题解 - 帖子 - CQUPT OJ

思路

观察发现，对于，每一个二进制位的贡献都是相互独立的，因此我们只需要讨论如何求算某个二进制位的贡献.

考虑的所有元素在第个二进制位下的情况，不妨定义和分别表示的已选前项元素的有效二进制位的加和为偶数和奇数的方案数。

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

由于的任意一项均允许选择数组中的任意一个元素，因此当仅考虑第个二进制位时，可以允许预处理出在第个二进制位下有效的元素数量，记为。此外，二进制位无效的元素数量为 . ()

显然，， . 初始化时，.

第个二进制位的贡献为，最终答案为 .

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;
}