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;

}