题目描述

给定一个数组 Ai，分别求其每个子段的异或和，并求出它们的和。或者说，对于每组满足 1 ≤ L ≤ R ≤ n 的 L, R ，求出数组中第 L 至第 R 个元素的异或和。然后输出每组 L, R 得到的结果加起来的值。

输入格式

输入的第一行包含一个整数 n 。

第二行包含 n 个整数 Ai ，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

样例输入

5
1 2 3 4 5

样例输出

39

提示

对于 30% 的评测用例，n ≤ 300 ；
对于 60% 的评测用例，n ≤ 5000 ；
对于所有评测用例，1 ≤ n ≤ 105，0 ≤ Ai ≤ 2^20 。

区间[l,r]的异或和可以表示为，这样原问题就变成了：求n+1个数两两异或之和，如果的二进制第 j 位为1（0），我们只需知道 [0,i-1] 这个区间内的数二进制第 j 位为0（1）的个数x，这样s[i]的第 j 位的贡献值为x*2^j；

#include<iostream>
#include<vector>
#include<map>
#define int long long
using namespace std;
const int N=1e5+10;
int a[N][30];
signed main(){
	int n;
	cin>>n;
	int x;
	for(int i=1;i<=n;i++){
		cin>>x;
		for(int j=0;j<=20;j++){
			a[i][j]=(x>>j)&1;
			a[i][j]^=a[i-1][j];
		}
	}
	int ans=0;
	for(int j=0;j<=20;j++){
		map<int,int> mp;
		mp[0]++;
		for(int i=1;i<=n;i++){
			int x=mp[a[i][j]^1];//与第i个数第j位不同的个数
			ans+=(1<<j)*x;
			mp[a[i][j]]++;
		}
	}
	cout<<ans<<endl;
	return 0;
}

#include<iostream>
#include<vector>
#include<map>
#define int long long
using namespace std;
const int N=1e5+10;
int a[N];
int s[N];
int cnt[N][30];
signed main(){
	int n;
	cin>>n;
	int x;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s[i]=s[i-1]^a[i];
	}
//求n+1个数第j位0和1的个数
	for(int j=0;j<=20;j++){
		for(int i=0;i<=n;i++){
			if(s[i]>>j&1) cnt[j][1]++;
			else cnt[j][0]++;
		}
	}
	int ans=0;
	for(int i=0;i<=20;i++){
//每个1都可以和每个0异或等于1，总数为cnt[i][0]*cnt[i][1]，每个1的贡献值为2^i
		ans+=cnt[i][0]*cnt[i][1]*(1<<i);
	}
	cout<<ans<<endl;
	return 0;
}