思路

​ 观察发现，对于 $V = a_{i_1} \oplus a_{i_2} \oplus .... \oplus a_{i_n}$，每一个二进制位的贡献都是相互独立的，因此我们只需要讨论如何求算某个二进制位的贡献.

​ 考虑$V$的所有元素在第 $p$ 个二进制位下的情况，不妨定义 $cnt_{0}[i]$ 和 $cnt_{1}[i]$ 分别表示 $V$的已选前 $i$ 项元素的有效二进制位的加和为偶数和奇数的方案数。

​ （一个元素$x$在第 $p$ 个二进制位下有效的含义是，该元素$x$的第 $p$ 个二进制位为1）

​ 由于 $V$ 的任意一项均允许选择数组 $a$ 中的任意一个元素，因此当仅考虑第 $p$ 个二进制位时，可以允许预处理出在第$p$个二进制位下有效的元素数量，记为 $v_{1}$。此外，二进制位无效的元素数量为 $v_{0}$. ($v_{0} + v_{1} = n$)

​ 显然， $cnt_{0}[i] = cnt_{0}[i - 1] * v_{0} + cnt_{1} [i - 1] * v_{1}$， $cnt_{1}[i] = cnt_{0}[i - 1] * v_{1} + cnt_{1} [i - 1] * v_{0}$. 初始化时，$cnt_{0}[0] = 1, cnt_{1}[0] = 0$.

​ 第$p$个二进制位的贡献为 $S_{p} = cnt_{1}[n] * 2^{p}$，最终答案为 $ans = \sum_{p = 0}^{29} S_{p}$.

Code

#include<bits/stdc++.h>
using namespace std;
const int P = 1000000007;

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    int n;
    std::cin>>n;
    std::vector<int>a(n);

    for(int i = 0;i < n;i++) {
        std::cin>>a[i];
    }

    int ans = 0;
    for(int i = 0;i < 30;i++) {
        int v0 = 0, v1 = 0;
        for(int j = 0;j < n;j++) {
            if(a[j] >> i & 1) {
                v1++;
            }else {
                v0 ++;
            }
        }
        int cnt0 = 1, cnt1 = 0;
        for(int j = 0;j < n;j++) {
            int c0 = (1LL * cnt0 * v0 + 1LL * cnt1 * v1) % P;
            int c1 = (1LL * cnt0 * v1 + 1LL * cnt1 * v0) % P;
            cnt0 = c0, cnt1 = c1;
        } 
        ans = (ans + (1LL << i) * cnt1 % P) % P;
    }
    
    std::cout<<ans<<"\n";

    return 0;
}