Readme

2527.Find-Xor-Beauty-of-Array

因为bit之间彼此互不影响，所以我们这里仅考虑一个bit位的情况。

我们要把所有可能的(a|b)&c进行异或。这里要注意，异或的本质是就是bit 1的个数。如果有奇数个bit 1进行异或，答案就是1；否则答案就是0. 所以在这里，我们只需要考虑数值为1的c。数值为0的c，只会贡献(a|b)&c=0，不影响结果。

当我们固定了c，接下来考虑所有a|b的配对，我们需要将这些0或1都异或起来。假设有总共有n个元素，其中有x个元素在这个bit上是1，剩下y个元素在这个bit上是0，那么我们选取到a|b=1的个数就是(n^2-y^2)个（即排除掉选到两个0的可能性）。我们发现(n^2-y^2)=(n+y)(n-y)=(n+y)x=(2n-x)x，说明(n^2-y^2)的奇偶性取决于x的奇偶性。也就是说，如果在这个bit位上有奇数个1，那么就有奇数个a|b的值是1，它们异或的结果就是1. 反之，它们异或的结果就是0. 如果用一个公示表达，那就是等于将所有元素的该bit都异或起来。

以上分析是针对固定的c。那么遍历所有的c，会遇到类似的情况。如果固定c对应的sum(a|b)是1，那么说明有奇数个c是1，再将奇数个答案异或起来，那还是1. 如果固定c对应的答案是0，那么说明所有的sum(a|b)都是0，最终答案还是0.

所以最终答案只需要将所有元素异或起来即可。