solution
计算区间异或和可以利用前缀异或和计算。因为n只有,所以只要在复杂度内解决就好了。
然后考虑如何保证区间不相交。枚举一个点。用表示右端点小于等于x的区间中异或和为的区间数量。然后枚举一下左端点大于x的区间,如果该区间的异或和为那么就将答案加上。
code
/* * @Author: wxyww * @Date: 2020-04-13 16:06:54 * @Last Modified time: 2020-04-13 16:21:01 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> #include<cstring> #include<algorithm> #include<string> #include<queue> #include<vector> using namespace std; typedef long long ll; const int N = 400010; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } int a[N],ma[N]; int main() { ll ans = 0,n = read(); for(int i = 1;i <= n;++i) a[i] = read() ^ a[i - 1]; for(int i = 1;i <= n;++i) { for(int j = 0;j < i;++j) ma[a[i] ^ a[j]]++; for(int j = i + 1;j <= n;++j) ans += ma[a[j] ^ a[i]]; } cout<<ans<<endl; return 0; }