【每日一题】Xorto题解

Solution

这是一道数组上的异或问题, 这类问题一般要使用前缀异或和作为辅助, 即
sum[i] = a[1] ^ a[2] ..... ^ a[i];
它具有这样的性质
sum[i] ^ sum[j - 1] = a[j] ^ a[j + 1] .... ^ a[i]; (i >= j)
其次我们要明白一个问题 两个区间异或为0 等价于 两个区间的异或和相等
再看到问题
我们考虑枚举一个边界i, 然后看以 i 为右端点的区间和 以 i 为左端点的区间里异或和相等的数量

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const ll mod = 998244353;
const int DEG = 20;
const double PI = acos(-1.0);
const double eps = 1e-10;
const ll inf = 1e18;
const int N = 1e6 + 5;
static auto faster_iostream = []() {
    std::ios::sync_with_stdio(false);  // turn off sync
    std::cin.tie(nullptr);             // untie in/out streams
    return 0;
}();
int a[N];
int sum[N];
map<int, int> mp;
int main(){
  int n;
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> a[i];
  for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] ^ a[i];
  ll ans = 0;
  for(int i = 1; i <= n; i++){
    for(int j = 0; j < i; j++){
      mp[sum[i] ^ sum[j]]++;
    }
    for(int j = i + 1; j <= n; j++){
      ans += mp[sum[i] ^ sum[j]];
    }
  }
  cout << ans << "\n";
  return 0;
}