2527-查询数组 Xor 美丽值

给你一个下标从 0 开始的整数数组 nums 。

三个下标 i ，j 和 k 的 有效值 定义为 ((nums[i] | nums[j]) & nums[k]) 。

一个数组的 xor 美丽值 是数组中所有满足 0 <= i, j, k < n 的三元组 (i, j, k) 的
有效值 的异或结果。

请你返回 nums 的 xor 美丽值。

注意：

• val1 | val2 是 val1 和 val2 的按位或。
• val1 & val2 是 val1 和 val2 的按位与。

示例 1：

**输入：** nums = [1,4]
**输出：** 5
**解释：**
三元组和它们对应的有效值如下：
- (0,0,0) 有效值为 ((1 | 1) & 1) = 1
- (0,0,1) 有效值为 ((1 | 1) & 4) = 0
- (0,1,0) 有效值为 ((1 | 4) & 1) = 1
- (0,1,1) 有效值为 ((1 | 4) & 4) = 4
- (1,0,0) 有效值为 ((4 | 1) & 1) = 1
- (1,0,1) 有效值为 ((4 | 1) & 4) = 4
- (1,1,0) 有效值为 ((4 | 4) & 1) = 0
- (1,1,1) 有效值为 ((4 | 4) & 4) = 4 
数组的 xor 美丽值为所有有效值的按位异或 1 ^ 0 ^ 1 ^ 4 ^ 1 ^ 4 ^ 0 ^ 4 = 5 。

示例 2：

**输入：** nums = [15,45,20,2,34,35,5,44,32,30]
**输出：** 34
**解释：** 数组的 xor 美丽值为 34 。

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109

如果这题暴力解，代码应该是这样的：

class Solution:
    def xorBeauty(self, nums: List[int]) -> int:
        n = len(nums)

        res = 0
        for i in range(n):
            for j in range(n):
                for k in range(n):
                    res ^= (nums[i] | nums[j]) & nums[k]
        
        return res
        

当然这题暴力肯定会超时，接下来我们来化简一下~

假设 nums = [a, b, c]，根据上面的暴力代码，我们可以计算所有 i, j, k 的有效值如下：

PS：一共是 3^3=27 个有效值，我们把它写成如下 3 x 3 分块矩阵~

(a | a) & a     (b | a) & a     (c | a) & a
(a | a) & b     (b | a) & b     (c | a) & b
(a | a) & c     (b | a) & c     (c | a) & c

(a | b) & a     (b | b) & a     (c | b) & a
(a | b) & b     (b | b) & b     (c | b) & b
(a | b) & c     (b | b) & c     (c | b) & c

(a | c) & a     (b | c) & a     (c | c) & a
(a | c) & b     (b | c) & b     (c | c) & b
(a | c) & c     (b | c) & c     (c | c) & c

根据 按位或 的 对称性，即 x | y = y | x，我们不难发现上面的分块矩阵是一个 对称矩阵，也就是说所有元素的 异或 等于对角线元素的 异或，我们保留 对角线元素(块)，得到如下 3 x 3 矩阵：

(a | a) & a     (b | b) & a     (c | c) & a
(a | a) & b     (b | b) & b     (c | c) & b
(a | a) & c     (b | b) & c     (c | c) & c

由于 a | a = a, a & a = a，我们将上面的矩阵再化简一下，有：

  a       b & a     c & a
a & b       b       c & b
a & c     b & c       c

再根据 按位与 运算的 对称性，即 x & y = y & x，我们不难发现，这又是一个 对称矩阵，所有元素的 异或 等于对角线元素的 异或，即：

a ^ b ^ c

因此，我们有如下结论：

nums 的 xor 美丽值即为 nums 所有元素的异或值。

最终代码如下：

[]

class Solution {
public:
    int xorBeauty(vector<int>& nums) {
        int res = 0;
        for (auto num: nums){
            res ^= num;
        }
        return res;
    }
};

[]

class Solution:
    def xorBeauty(self, nums: List[int]) -> int:
        res = 0
        for num in nums:
            res ^= num
        
        return res