P9236 [蓝桥杯 2023 省 A] 异或和之和题解

思路

题目给我们一个数组 \(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;
}

参考文献：

https://www.luogu.com.cn/blog/w9095/solution-p9236