https://codeforces.com/contest/1113/problem/C
题意
一个n个数字的数组a[],求有多少对l,r满足\(sum[l,mid]=sum[mid+1,r]\),sum为异或和(n<=3e5,a[i]<=2^20)
题解
- 异或和为零的区间可以分成任意两个区间(这两个区间的异或和相等)
- 定义dp[i][j]为异或和为i,下标为j(只记录奇偶)的前缀个数
- 枚举r,然后累加l
代码
#include<bits/stdc++.h>
#define M 3000005
#define ll long long
using namespace std;
ll f[M][3],a[M],ans;
int n,i;
int main(){
cin>>n;
for(i=1;i<=n;i++){scanf("%lld",&a[i]);a[i]^=a[i-1];}
f[0][0]=1;
for(i=1;i<=n;i++){
ans+=f[a[i]][i%2];
f[a[i]][i%2]++;
}
cout<<ans;
}