官方题解,很详细了 第一次学到异或还能求前缀和,斯巴拉西. 枚举区间的方法也是第一次学到. sum[i]代表a1~ai的异或和, 那么题目等价于求多少对l~r 使得sum[l-1]=sum[r] 因为要求区间长度为偶数 当r为奇数时 l一定是偶数 那么l-1就是奇数,反过来也一样 .所以最后等价于 对当前枚举的i,i前面有多少与i奇偶性相同的sum[i],开了个map记录下就行. 唯一需要注意的就是 mp[0][0]的初始值为1,看了很多博客也没具体明白为什么 ,可能意思代表长度为0时异或为0也在数组中(猜的) 举个例子,输入为 2 1 1 如果不初始化 最后答案就是0 因为当i等于2时 mp[0][0]为0 ans+=mp[0][0] 导致对答案没贡献
#include<cstdio> #include<cstring> #include<cmath> #include<string> #include<iostream> #include<vector> #include<map> #include<set> #include<stack> #include<queue> #include<stdlib.h> #include<algorithm> #include<time.h> #include<unordered_map> #define bug1(g) cout<<"test: "<<g<<endl #define bug2(g,i) cout<<"test: "<<g<<" "<<i<<endl #define bug3(g,i,k) cout<<"test: "<<g<<" "<<i<<" "<<k<<endl #define bug4(a,g,i,k) cout<<"test: "<<a<<" "<<g<<" "<<i<<" "<<k<<endl using namespace std; typedef long long ll; unordered_map<int,int>mp[2]; int main() { ios::sync_with_stdio(0); ll n,x,a,ans=0; cin>>n; mp[0][0]=1; x=0; for(int i = 1;i<=n;i++) { cin>>a; x^=a; ans+=mp[i%2][x]; ++mp[i%2][x]; } cout<<ans<<endl; return 0; }