形式化题目

给定长度为 $n$ 的非负整数序列 $A_1, A_2, \dots, A_n$，求

即所有连续子段的按位异或和之总和。其中 $1 \leqslant n \leqslant 10^5$，$0 \leqslant A_i \leqslant 2^{20}$，答案唯一，不存在多解。

子段一共有 $\frac{n(n+1)}{2}$ 个：$n = 300$ 时约 $4.5 \times 10^4$ 个，$n = 5000$ 时约 $1.25 \times 10^7$ 个，而 $n = 10^5$ 时约 $5 \times 10^9$ 个。这个数量级的变化，正是本题全部难度的来源。

暴力解法

思路

最直接的做法就是照着定义做：枚举左端点 $L$，再让右端点 $R$ 从 $L$ 一路右移，边走边维护当前子段的异或和。

关键是这样向右扩展时不需要重新算整段：异或满足

所以每往右多吞一个数，只要把现在的异或和再异或上 $A_R$ 即可，单步是 $O(1)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-03 11:01
 * update_at: 2026-10-03 11:01
 */
// brute.cpp：小数据暴力解，直接枚举所有子段求异或和，用来对拍 main.cpp。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 1e5 + 5;

int n;
int a[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // 枚举左端点 L，向右扩展右端点 R，边走边维护当前子段的异或和
    ll ans = 0;
    for (int L = 1; L <= n; L++) {
        int now = 0;
        for (int R = L; R <= n; R++) {
            now ^= a[R];   // [L, R] 的异或和
            ans += now;
        }
    }

    cout << ans << "\n";
    return 0;
}

复杂度

外层 $L$ 有 $n$ 种，内层 $R$ 平均走 $n/2$ 步，时间 $O(n^2)$，空间 $O(n)$。

瓶颈

$n = 10^5$ 时需要约 $5 \times 10^9$ 次加法，远超时限。瓶颈在于：我们把每个子段都当成一个独立对象去计算它的异或值。

可是题目并不要求我们输出每个子段的异或值，只要求它们的和。那就有机会绕开“逐个算异或值”这一步——只要能直接数出“有多少个子段在某一位上是 $1$”，加权求和即可。这正是正解的突破口。

正解

思路

第一步：把子段异或换成两个前缀异或的异或。

令 $P_0 = 0$，$P_i = A_1 \oplus A_2 \oplus \cdots \oplus A_i$。由异或的消去律 $x \oplus x = 0$，中间部分会两两抵消：

于是“子段 $(L, R)$”与“下标对 $(L-1, R)$”一一对应，且这个对应保持运算结果不变。注意 $P_0$ 必须参与，它代表空前缀——少了它，以 $A_1$ 开头的子段就丢了。

第二步：拆位。

我们关心的不是 $P_R \oplus P_{L-1}$ 这个数具体是多少，而是它的每一位。设第 $k$ 位的位权是 $2^k$，并设所有子段中第 $k$ 位为 $1$ 的有 $c_k$ 个，那么

这是合法的，因为二进制表示下每一位的贡献可以单独相加，不会互相干扰。

第三步：$c_k$ 变成两个计数的乘积。

$P_R \oplus P_{L-1}$ 的第 $k$ 位为 $1$，等价于 $P_R$ 和 $P_{L-1}$ 在这一位上不同（一个 0 一个 1）。所以只要数一数前缀数组 $P_0, P_1, \dots, P_n$ 中：

• 第 $k$ 位是 $0$ 的有 $cnt_0$ 个；
• 第 $k$ 位是 $1$ 的有 $cnt_1$ 个。

那么从 0 组里挑一个下标、从 1 组里挑一个下标，得到的下标对异或后第 $k$ 位必为 $1$；反过来任何第 $k$ 位为 $1$ 的下标对也必然是一边 0 一边 1。两组下标无先后要求：小的那个当下标 $L-1$、大的那个当 $R$ 就得到一个合法子段。因此

到这里，原来看起来必须逐个枚举的 $O(n^2)$ 个异或值，被压缩成 $31$ 次“数 0 和数 1”。

第四步：按位循环统计。

$A_i \leqslant 2^{20}$，异或不会把位升高，所以 0 到 20 位就够了。为了不踩边界，代码里统一统计到第 30 位：更高的位 $cnt_1$ 恒为 0，乘出来是 0，不会污染答案。

用样例检验一遍。 样例 $A = [1, 2, 3, 4, 5]$，前缀异或为

逐位统计：

合计 $9 + 10 + 20 = 39$，与题面样例一致。

正确性说明。 三处推导各自成立：前缀异或恒等式由消去律保证；拆位相加由二进制表示的唯一性保证；$c_k = cnt_0 \cdot cnt_1$ 是一一对应的计数，既不会漏也不会重。因此算法输出恰好等于定义中的求和。

溢出提醒。 最大可能答案是

int 装不下，必须用 long long。另外单看乘积 $cnt_0 \cdot cnt_1$ 最大也可达 $2.5 \times 10^9$，所以乘积本身也要在 64 位里做（C++ 中 (1LL << k) * cnt[0] * cnt[1] 因为最左边是 long long，整个表达式会自动提升，这样写是安全的）。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-03 11:01
 * update_at: 2026-10-03 11:01
 */
// P9236 [蓝桥杯 2023 省 A] 异或和之和
// 正解：按位统计前缀异或的 0/1 个数。
// 第 k 位对答案的贡献 = 2^k * (该位上 c[0] * c[1])
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int maxn = 1e5 + 5;

int n;
int a[maxn];
int pre[maxn]; // pre[i] = a[1] ^ a[2] ^ ... ^ a[i]

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // 预异或：pre[0] = 0，pre[i] = pre[i-1] ^ a[i]
    pre[0] = 0;
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1] ^ a[i];
    }

    ll ans = 0;
    // 逐位统计。A_i <= 2^20，再加上可能出现的进位，到 20 位足够；
    // 多算几位也不会错，这里写到 30 位纯粹为了保险。
    for (int k = 0; k <= 30; k++) {
        ll cnt[2] = {0, 0};
        // 统计前缀异或数组 pre[0..n] 中第 k 位为 0 / 1 的个数
        for (int i = 0; i <= n; i++) {
            cnt[(pre[i] >> k) & 1]++;
        }
        // 一 0 一 1 的下标对 (L-1, R) 恰好满足 pre[L-1] != pre[R]，
        // 也就是区间 [L, R] 的异或和第 k 位为 1，共 cnt[0] * cnt[1] 个区间
        ans += (1LL << k) * cnt[0] * cnt[1];
    }

    cout << ans << "\n";
    return 0;
}

复杂度

预处理前缀异或 $O(n)$，之后对每个二进制位扫描一遍前缀数组，共 $31$ 次，总计时间 $O(31n)$（即 $O(n \log \max A)$）。$n = 10^5$ 时约 $3.1 \times 10^6$ 次操作。空间 $O(n)$ 存前缀异或数组（若边读边算，还可以降到 $O(1)$）。

总结

本题的推导链条是：

1. 换对象：子段异或不好直接算，用前缀异或换成两个下标值的异或（别忘了 $P_0$）；
2. 换问题：不需要知道每个异或值，只要求总和，于是拆位，把“求和”变成“数个数”；
3. 换计数：某一位为 $1$ 的异或值个数，正好是“该位为 0 的前缀个数 × 该位为 1 的前缀个数”。

三步的共同点是：每一步都在把更“贵”的对象替换成更“便宜”的等价的量——先去掉区间、再去掉具体数值、最后去掉枚举。这也是处理异或类统计问题最常用的套路：异或的每一位互不干扰，遇到求和就拆位，遇到区间异或就转前缀。

需要留心两个坑：$P_0$ 必须统计进去；答案和中间乘积都要用 64 位整数。