【题解】P3917 异或序列

传送门

也算是一个有关于异或的小 trick 吧，简单记录一下。

可以维护原序列的前缀异或和 \(sum\)，于是原题答案贡献变为 \(\sum\limits_{i=1}^n \sum\limits_{j=i}^n sum_j \oplus sum_{i-1}\)。变形一下为 \(\sum\limits_{i=0}^{n-1} \sum\limits_{j=1}^{i+1} sum_i \oplus sum_{j}\)。发现按照常规的方法做不动了。

于是我们换一种思路，按照二进制位统计贡献。因为异或的特殊性，“相同为1，不同为0”。只有当同一位上的状态不同时（0/1 or 1/0）才能对答案做出贡献。记 \(cnt_{i,0/1}\) 表示在已统计过的所有数中第 \(i\) 位的 \(0/1\) 的个数。

考虑如何统计答案。假设枚举到了第 \(i\) 位，前 \(i-1\) 位的 \(cnt\) 贡献已经计入桶中。则当前位的答案贡献为：

1. 若当前 \(a_i\) 第 \(j\) 位为 \(0\)，则一共能作出 \(2^j\times cnt_{j,1}\) 的贡献。因为当前位的 \(0\) 能和之前所有的 \(1\) 形成 \(2^j\) 的贡献，总共为 \(2^j\times cnt_{j,1}\)；

2. 同理。若当前 \(a_i\) 第 \(j\) 位为 \(1\)，则一共能作出 \(2^j\times cnt_{j,0}\) 的贡献。

最后将位置 \(i\) 的 \(cnt\) 贡献加入即可。答案一边枚举一边统计。

时间复杂度从 \(O(n^2)\) 优化至 \(O(n)\)。

#include<bits/stdc++.h>
#define int long long
#define For(i,l,r) for(int i=l;i<=r;++i)
#define FOR(i,r,l) for(int i=r;i>=l;--i)

using namespace std;

const int N = 1e5 + 10;

int n, sum[N], cnt[N][2], ans;

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n;
  For(i,0,30) cnt[i][0] = 1;
  For(i,1,n) {
    int x; cin >> x;
    sum[i] = sum[i-1] ^ x;
    FOR(j,30,0) {
      if((sum[i] >> j) & 1) {
        ans += (1 << j) * cnt[j][0];
        cnt[j][1]++;
      } else {
        ans += (1 << j) * cnt[j][1];
        cnt[j][0]++;
      }
    }
  }
  cout << ans << '\n';
  return 0;
}