思路
题目给我们一个数组 \(a\)，那么我们可以算出其异或前缀和 \(sum\)。
我们知道，算出 \([l, r]\) 的异或和可以这样计算：\(sum_r \oplus sum_{l - 1}\)。
那么问题就转换为了 \(sum_{0\sim n}\) 这 \(n + 1\) 个数字两两异或之和（当然 \(sum_i \oplus sum_j\) 和 \(sum_j\oplus sum_i\) 是一样的，不重复计算）。
那我们遍历 \(sum\) 数组，然后计算出 \(w_{i, j}\) 数组表示所有数字在二进制表示下第 \(i\) 位为 \(j\) 的数字个数（\(0 \le i \le 20, 0 \le j \le 1\)）。
对于第 \(i\) 位，如果有两个数字的第 \(i\) 位分别为 \(0, 1\)，那么就可以贡献 \(2^i\) 的和。
根据乘法原理，对于第 \(i\) 位可以凑出 \(w_{i, 0}\cdot w_{i, 1}\) 这么多对可以对答案有贡献的组合，它们的贡献都是 \(2 ^ i\)，所以可以让 \(ans\) 加上 \(w_{i, 0}\cdot w_{i, 1}\cdot2^i\)。
代码
注意要开 long long。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 100010, M = 25;
int n;
int a[N];
int w[M][2];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i], a[i] ^= a[i - 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j < M; j++) {
w[j][a[i] >> j & 1] ++;
}
}
i64 ans = 0;
for (int i = 0; i < M; i++) ans += (1ll * w[i][0] * w[i][1] * (1 << i));
cout << ans << '\n';
return 0;
}
参考文献：