P3917 异或序列

纯暴力\(\Theta(n^3)\)，前缀和优化\(\Theta(n^2)\)，因\(n\)为十万级别无法通过本题。

考虑将每个二进制位的贡献分开来算。

对于二进制第\(i\)位，若当前此位为1，则只有与0亦或才能产生贡献，反之亦然。

则对于每一个二进制位，维护数组\(val[i][0/1]\)，代表这个位置上\(0/1\)的个数。

则贡献为\(w=val[i][!t]*(1<<i)\)，注意总贡献要开\(long long\)。

注意对于每个数只计算它与前面产生的贡献，这样就不会重复计算。

时间复杂度\(\Theta(nlogn)\)

代码如下，仅供参考：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n,a[maxn];
inline int read(){
	int 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<<1)+(x<<3)+c-‘0‘;c=getchar();}
	return x*f;
}
int val[50][2],cnt;
long long ans;
inline void insert(int x){
	for(int i=0;i<=30;i++){
		int t=(((1<<i)&x)!=0);
		ans+=(1ll<<i)*val[i][!t];
		val[i][t]++;
	}
}
int main(){
	n=read();
	for(int i=1;i<=n;i++)
		a[i]=read()^a[i-1];
	insert(0);
	for(int i=1;i<=n;i++)
		insert(a[i]);
	printf("%lld\n",ans);
	return 0;
}

深深地感到自己的弱小。

P3917 异或序列

原文：https://www.cnblogs.com/syzf2222/p/13866815.html