转载自：https://blog.csdn.net/Charles_Zaqdt/article/details/87522917
题目链接：https://codeforces.com/contest/1113/problem/C
题意是给了n个数字，让找出一个长度为偶数的区间[l, r]，使得al ^ al+1 ^ .... ^ amid = amid + 1 ^ ... ^ ar这个等式成立(l到mid的异或和等于mid+1到r的异或和)，求出有多少个满足要求的区间。
想要满足上述要求，即左边等于右边，那么整段l到r区间的抑或和的结果为0。那么反过来区间异或值为0，左边和右边相等吗？答案是肯定的。（其实任意分的两段都相等）。
同时由于异或满足类似于加法和减法性质，即如果a^b=c，则c^a=b,c^b=a。所以这里我们可以想到用抑或前缀和，因为我们可以理用前缀和很快的查找pre[r]^pre[l-1]得到这一段的抑或值，所以这道题就变成了求前缀抑或和的pre[r] - pre[l-1] = 0 而且l到r的长度必须是偶数的个数有多少个，其实判断长度为偶数也不是很难，我们把每一位前缀抑或和都按顺序标记上奇偶，对于r和l-1位置的奇偶性相同的话，这个区间就一定是长度为偶数的区间。
那么这道题就变成了寻找pre[r] = pre[l-1] 且 r位置和l-1位置的奇偶性相同的区间有多少个了，还有要注意的是第二个样例中求出来了pre前缀异或和的数组中有0的存在，也就是前4个的异或和为0也是符合要求的，那么对于这种数据的处理，我们可以在第0位加一个0就好了，就像第二个样例，pre[4] = pre[1-1] = 0，这样也是符合要求的，还有就是如果有多个符合要求的数，求的应该是他们的组合数，比如说求出来的前缀和是3 3 3 3那么方案就是1 + 2 + 3。
大致思路就是这样，写法有很多种，我的写法是用map+pair实现的，用map标记(这个数和这个数的奇偶性)出现的次数。
AC代码：
1 #include<cstdio> 2 #include<map> 3 using namespace std; 4 5 typedef long long LL; 6 typedef pair<int, int> P; 7 map<P, int>ma; 8 9 int main() 10 { 11 int n; 12 scanf("%d", &n); 13 ma[P(0, 0)] = 1; //补充一个(0,0) 14 int pre = 0; //异或前缀和 15 LL ans = 0; 16 for (int i = 1; i <= n; i++) 17 { 18 int tmp; 19 scanf("%d", &tmp); 20 pre ^= tmp; 21 ans += ma[P(pre, i % 2)]++; 22 } 23 printf("%I64d ", ans); 24 return 0; 25 }