异或和之和 题解

bochibochi · 2023-05-16 14:11:33 · 题解

由异或操作可以想到拆位，对于数的每一位计算异或和。显然，如果第 k 位有 x 个区间异或和是 1，那么对答案的贡献就是 x\times 2^k。

某个区间异或和为 1 等价于这个区间中存在奇数个 1，因此只需要对于每个位置 i 计算 S_i=\sum_{j=1}^ia_j，然后统计奇偶性不同的数对 S_i,S_j 数量即可。

#include<iostream>
using namespace std;
int a[100005];
int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    long long ans = 0;
    for(int k = 0; k <= 22; k++)
    {
        int x = 1, y = 0, s = 0;
        long long res = 0;
        for(int i = 0; i < n; i++)
        {
            if(a[i] & (1<<k)) s ^= 1;
            if(s) res += x, y++;
            else res += y, x++;
        }
        ans += res<<k;
    }
    cout << ans;
    return 0;
}