1
2
2
1 2

1
6

我们知道，按位异或具有位独立性，即位与位之间的运算是独立的，因此可以按位计算贡献．

对于子串贡献题，最常见的是使用 dp，定义 dp[i] 表示以第 $i$ 个数结尾能够做出的贡献．由于异或具有位独立性，因此，对状态稍作修改，定义状态 dp[i][j] 表示只考虑每一个数的第 $j$ 位，以第 $i$ 个数为结尾的子串中异或和为 1 的数量．即若设 $s_{i,j}$ 表示 $s_i$ 的第 $j$ 位，则 $dp_{i,j}$ 为 $\forall k \leq i$，满足 $s_{k,j}\oplus s_{k+1, j}\oplus s_{k+2, j}\cdots \oplus s_{i,j}=1$ 的 $k$ 的数量．

这样就可以开始 dp 了，对于每一位 $j$，初始状态为 $dp_{1, j}=s_{1,j}$，接着，遍历每一个数，设遍历到第 $i$ 个数，则：

• 若 $s_{i, j}=0$，
  • 对于以 $i$ 结尾且长度为 1 序列，其异或和为 0，故对答案没有贡献．
  • 对于以 $i$ 结尾且长度为 $k,k>1$ 的序列，其异或和为不会发生改变，因此原来以 $i-1$ 结尾，长度为 $k-1$ 的序列异或了 0 之后值仍不变．因此，这种情况对答案的贡献就是以 $i-1$ 结尾的序列中异或和为 1 的序列数量．
  • 因此存在转移方程：$dp_{i, j}=dp_{i-1, j}$．
• 若 $s_{i,j}=1$，
  • 对于以 $i$ 结尾且长度为 1 序列，其异或和为 1，对答案贡献为 1．
  • 对于以 $i$ 结尾且长度为 $k,k>1$ 的序列，其异或和会改变，因此原来以 $i-1$ 结尾，长度为 $k-1$ 的序列异或了 1 之后原来是 1 的会变成 0，原来是 0 的会变成 1．因此，这种情况对答案的贡献就是以 $i-1$ 结尾的序列中异或和为 0 的序列数量．使用总序列数量 $i-1$，减去为 1 的序列数量 $dp_{i-1,j}$ 即可．
  • 因此存在转移方程：$dp_{i,j}=i-1-dp_{i-1,j}+1=i-dp_{i-1,j}$．

对于答案，我们需要统计以每一个数结尾的子串每一位的贡献，即：

可以写出标程．由于 $dp_{i,j}$ 只与 $dp_{i-1,j}$ 有关，故可以把 $dp$ 数组变成一个变量 ans 以达到节省空间的效果，以下标程实现了这个效果．

标程

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
const int N = 2e6 + 100;
5
int a[N], ans;
6

7
signed main() {
8
    ios::sync_with_stdio(false);
9
    cin.tie(0);
10
    cout.tie(0);
11
    int n;
12
    cin >> n;
13
    for (int i = 1; i <= n; i++) {
14
        cin >> a[i];
15
    }
16
    for (int i = 0; i < 32; i++) {
17
        int now = (a[1] >> i) & 1;
18
        ans += now * (1 << i);
19
        for (int j = 2; j <= n; j++) {
20
            if (a[j] & (1 << i)) {
21
                now = j - 1 - now + 1;
22
            }
23
            ans += now * (1 << i);
24
        }
25
    }
26
    cout << ans;
27
    return 0;
28
}