题解 | #小美的区间异或和#

对于连续子数组，考虑状态定义代表了以结尾的数组的异或和。由于代表了，他是一定包括了，所以。

然后对于新出现的,可以通过例子，不妨用题目给出的例子。

对于以索引3结尾(从0开始),有如下3个连续子数组：

[1,2],[3,1,2],[2,3,1,2]。

我们可以发现索引2位置异或了3次，索引1位置异或了2次，索引0位置异或了1次。

通过上面的例子我们可以发现，其实异或的次数是固定的。但是异或并不满足结合律，不能够拆，那么我们不妨对每一个数拆位，这样就变为了一个01序列，由于是异或运算，可以直接通过前缀中1或者0的个数求解。

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
    int n; cin >> n;
    int a[n];
    for(int i = 0; i < n; i++) cin >> a[i];
    int f[n + 1];
    memset(f,0,sizeof(f));
    int cnt[32][2];
    memset(cnt,0,sizeof(cnt));
    int res = 0;
    for(int i = 0;i < n;i++){
        f[i + 1] = f[i];
        for(int j = 0;j < 32;j++){
            int bit = (a[i] >> j) & 1;
            f[i + 1] += cnt[j][bit ^ 1] * (1 << j);
            f[i + 1] %= MOD;
            //维护的是出现的个数。
          	cnt[j][bit] = cnt[j][bit] + i + 1;
            cnt[j][bit] %= MOD;
        }
    }
    for(int i = 1;i <= n;i++){
        res += f[i];
        res %= MOD;
    }
    cout << res << endl;
    
    return 0;
}