【每日一题】Xorto

Solution

(用表示异或运算)

因为当且仅当时才有，所以题目要求的就是有多少对区间的异或和相等且不重叠。

设为右端点小于且异或和为的区间的个数，此时，若区间的异或和为，那么它对答案的贡献为。

枚举，首先对所有左端点为的区间计算贡献，然后利用右端点为的区间来更新。

总复杂度。

Code

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int a[1005], sum[1 << 17];
vector<int> add[1005], query[1005];

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

  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int l = 1; l <= n; l++) {
    int xorsum = 0;
    for (int r = l; r <= n; r++) {
      xorsum ^= a[r];
      add[r].push_back(xorsum);
      query[l].push_back(xorsum);
    }
  }
  ll res = 0;
  for (int i = 1; i <= n; i++) {
    for (auto v : query[i]) {
      res += sum[v];
    }
    for (auto v : add[i]) {
      ++sum[v];
    }
  }
  cout << res << "\n";
}