2527. 查询数组异或美丽值

链接: 2527. 查询数组异或美丽值

第 95 场双周赛 Q3 1550(假分数)

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

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

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

请你返回 nums 的异或美丽值。

注意:

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

需要一个 $o(n)$ 的时间复杂度

题解

0x3f

可能有的同学猜了个结论过了，但如果我把问题中的「异或」换成「求和」，阁下又该如何应对?

---

位运算经典技巧: 由于每个比特位互不相干，所以拆分成每个比特位分别计算。

• 由于只有 $0$ 和 $1$，这样就好算了。

对异或有影响的是 1，所以只需要统计 $(a \mid b) \& c=1$ 的情况。

那么 $c$ 必须是 $1$， a 和 b 不能都是 0 。

设有 $y$ 个 $1$，那么就有 x=n-y 个 0 。

那么 $c$ 有 $y$ 个， $a \mid b$ 有 $n^{2}-x^{2}$ 个（任意选是 $n^{2}$，减去两个都是 $0$ 的 $x^{2}$ 个）。

根据乘法原理，一共可以产生

$\text { ones }=\left(n^{2}-x^{2}\right) y=\left(n^{2}-(n-y)^{2}\right) y=\left(2 n y-y^{2}\right) y$

个 $1$。

由于异或只在乎 $ones$ 的奇偶性，所以 $2ny$ 可以去掉，那么就变成看 $y^{3}$ 的奇偶性，也就是 $y$ 的奇偶性。

如果 $y$ 是奇数，那么这个比特位的异或值就是 $1$。

这实际上就是看每个比特位的异或值是否为 $1$。

那么把 $nums$ 的每个数异或起来，就是答案。

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

C++

还有高手

对于每一个三元组

$(i,j,k) = (j,i,k)$ 相同，他们异或得 $0$，可以不考虑

剩下 $(a,α,b)$ 形式的三元组。此时可以化为二元组 $(a,6) = nums[a] \& nums[b]$

此时有 $(a,b) = (b,α)$

因此只剩下 $(i,i)$ 形式的二元组，即为 $nums[i]$

也就是把所有数异或起来即可