NC14247 Xorto

题目地址：

https://ac.nowcoder.com/acm/problem/14247

基本思路：

这题的重点在于我们要了解异或前缀和的概念,根据 a^b=c,a=c^b,b=c^a这个性质(我记得这个性质在两数交换中也有应用),我们可以知道异或运算同样满足使用前缀和的条件,即我们预处理sum[i] = sum[i-1]^a[i]那么区间[l,r]范围内的异或和就为sum[r] ^ sum[l-1]；
那么了解了这个概念这道题就很好做了,我们对于每个点i枚举它前面的所有区间异或值,再枚举它后面的所有区间异或值(注意i这个位置不能重叠),两者当中相等的,就是能满足条件的,我们用map记录一下之前出现的,在之后出现相同值的时候加一下map里的贡献就好了。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF 0x3f3f3f3f

const int maxn = 1010;
int n,a[maxn],sum[maxn];
int memo[1000010];
signed main() {
  IO;
  cin >> n;
  rep(i, 1, n) cin >> a[i];
  rep(i, 1, n) sum[i] = sum[i - 1] ^ a[i]; //预处理异或前缀和;
  int ans = 0;//注意要开longlong,我这里是全局longlong;
  rep(i, 1, n) {
    rep(j, 1, i) memo[sum[i] ^ sum[j - 1]]++;//记录下这些值出现的次数;
    rep(j, i + 1, n) ans += memo[sum[j] ^ sum[i]];//i包括在上面的区间里了,所以这里不算到;
  }
  cout << ans << '\n';
  return 0;
}