首先只有两个相同的数异或结果才可能为0即两个非重叠区间异或和应该相同
而求一个区间[l,r]的异或和可以用前缀异或和求得即sum[r]^sum[l-1]
然后枚举一个区间[x,y],规定这个区间[x,y]为右区间,固定右区间的左键为i,那么区间右键可以为i+1,i+2......,n,那么只要左区间的异或和等于右区间且左区间的右键小于x就可以了,每次循环更新以i-1位右键的所有异或和出现次数,因此计算[x,y]为右区间时的有几个左区间满足就是[x,y]这个区间的异或和之前出现的次数
#include <cstdio> #include <map> using namespace std; const int N = 1e3+10; map<int,int> mp; typedef long long ll; int n,sum[N]; ll ans; int main(){ scanf("%d",&n); for(int i = 1;i <= n;i++){ scanf("%d",sum+i); sum[i] ^= sum[i-1]; } for(int i = 1;i <= n;i++){ for(int j = i;j <= n;j++){ ans+=mp[sum[i-1]^sum[j]]; } for(int j = 0;j < i;j++){ mp[sum[i]^sum[j]]++; } } printf("%lld\n",ans); return 0; }