牛客NC14247 Xorto 异或前缀和

题目链接
时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述
给定一个长度为n的整数数组，问有多少对互不重叠的非空区间，使得两个区间内的数的异或和为0。

输入描述
第一行一个数n表示数组长度；
第二行n个整数表示数组；
1<=n<=1000,0<=数组元素<100000

输出描述
一行一个整数表示答案

输入
3
0 0 0

输出
5

说明
([1,1],[2,2]),([1,1],[3,3]),([1,1],[2,3]),([1,2],[3,3]),([2,2],[3,3])

这道题需要用到异或神奇的性质：
设xorsum[n]是异或前缀和数组, ⊕ oplus ⊕表示异或
x o r s u m [ n ] = a 1 ⊕ a 2 ⊕ a 3 … … ⊕ a n xorsum[n]=a_1oplus a_2oplus a_3……oplus a_n xorsum[n]=a1​⊕a2​⊕a3​……⊕an​
当我们想表示一个区间的异或和时，可以像利用前缀和数组求区间和一样，利用异或前缀和数组求区间异或和：
s o r s u m [ i , j ] = x o r s u m [ i − 1 ] ⊕ x o r s u m [ j ] sorsum[i,j]=xorsum[i-1]oplus xorsum[j] sorsum[i,j]=xorsum[i−1]⊕xorsum[j]
证明
x o r s u m [ i , j ] = a i ⊕ a i + 1 … ⊕ a j xorsum[i,j]=a_ioplus a_{i+1}…oplus a_j xorsum[i,j]=ai​⊕ai+1​…⊕aj​
x o r s u m [ i − 1 ] = a 1 ⊕ a 2 … ⊕ a i − 1 xorsum[i-1]=a_1oplus a_2 …oplus a_{i-1} xorsum[i−1]=a1​⊕a2​…⊕ai−1​
x o r s u m [ j ] = a 1 ⊕ a 2 … ⊕ a i − 1 ⊕ a i … ⊕ a j xorsum[j]=a_1oplus a_2…oplus a_{i-1}oplus a_i…oplus a_j xorsum[j]=a1​⊕a2​…⊕ai−1​⊕ai​…⊕aj​
x o r s u m [ i − 1 ] ⊕ x o r s u m [ j ] = ( a 1 ⊕ a 2 … ⊕ a i − 1 ) ⊕ ( a 1 ⊕ a 2 … ⊕ a i − 1 ⊕ a i … ⊕ a j ) xorsum[i-1]oplus xorsum[j]=(a_1oplus a_2 …oplus a_{i-1})oplus (a_1oplus a_2…oplus a_{i-1}oplus a_i…oplus a_j) xorsum[i−1]⊕xorsum[j]=(a1​⊕a2​…⊕ai−1​)⊕(a1​⊕a2​…⊕ai−1​⊕ai​…⊕aj​)
= ( a 1 ⊕ a 2 … ⊕ a i − 1 ) ⊕ ( a 1 ⊕ a 2 … ⊕ a i − 1 ) ⊕ ( a i … ⊕ a j ) =(a_1oplus a_2 …oplus a_{i-1})oplus (a_1oplus a_2 …oplus a_{i-1})oplus (a_i…oplus a_j) =(a1​⊕a2​…⊕ai−1​)⊕(a1​⊕a2​…⊕ai−1​)⊕(ai​…⊕aj​)
由异或的性质可以知道， a ⊕ a = 0 , 0 ⊕ b = b aoplus a=0,0oplus b=b a⊕a=0,0⊕b=b
于是1 ~i-1消去得0,0与i ~j异或得i ~j。
= a i … ⊕ a j =a_i…oplus a_j =ai​…⊕aj​

有了这一结论，可以做题了，题目让求有多少对互不重叠的区间异或和为0，由说明可以知道这里不重叠要求左区间的右端点和右区间左端点不能重合。
先处理异或和为0：由异或的性质可知，两个异或和相同的区间异或和为0
问题变为求多少对互不重叠区间异或和相同。
我们在区间中间取一个点i，第一层循环枚举i的位置，第二层循环先枚举以它为右端点的所有区间（j,i），再枚举以i+1为左端点的所有区间(i+1,j)，这两部分区间肯定互不重叠。用一个数组记录下左边部分找到的每个异或和的数量，在右边部分只要找到了存在于左边的异或和，就在总的结果里加上它的数量。
如在左边找到某个区间异或和为3，num[3]++,找到某个区间异或和为6，num[6]++,又找到某个区间异或和为3，num[3]++……
在右边区间找到某个区间和为3，就ans+=num[3],总的结果多了两对符合条件的区间。
这样是O(N^2)的复杂度，给的数据n<=1000
10 ^6<10 ^8（1秒运算量） 不会超时。

#include
using namespace std;
int xorsum[1005],num[1000005];//注意这里虽然题目给的数据是100000，但我们开数组需要多开一位，如100000^011111,得到111111，比100000大了
int main(){
	int n,i,j;
    long long ans=0;//结果可能很大
	cin>>n;
	for(i=1;i<=n;i++){
		int x;
		cin>>x;
		xorsum[i]=xorsum[i-1]^x; //求异或前缀和 
	}
	for(i=1;i<=n;i++){
		for(j=0;j//注意这里j≠i，j代表了j+1到i这个区间
			num[xorsum[j]^xorsum[i]]++;
		}
		for(j=i+1;j<=n;j++){
			ans+=num[xorsum[i]^xorsum[j]];
		}
	}
	cout<