题解：对每一位分别考虑贡献
先求前缀和
按照二进制减法分类讨论，求出最终这一位是1还是0
用树状数组维护
注意：树状数组对0这个位置单独考虑
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int u=1000000;
const int maxn=100009; int n;
int ans;
int a[maxn]; inline int lowbit(int x){
return x&(-x);
}
inline int Ct(int x,int y){
return x%(1<<y);
}
struct FenwickTree{
int c[u+10];
int cnt0;
void Add(int x,int val){
if(x==0){
cnt0+=val;
}else{
while(x<=u){
c[x]+=val;
x+=lowbit(x);
}
}
}
int Querysum(int x){
int ret=0;
while(x){
ret+=c[x];
x-=lowbit(x);
}
return ret+cnt0;
}
void Cle(){
cnt0=0;
memset(c,0,sizeof(c));
}
}T[2]; int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
for(int i=1;i<=n;++i)a[i]+=a[i-1]; for(int j=1;j<=21;++j){
T[0].Cle();T[1].Cle();
T[0].Add(0,1);
for(int i=1;i<=n;++i){
int tmp=Ct(a[i],j-1);
int cnt=0;
if(a[i]&(1<<(j-1))){
cnt+=T[0].Querysum(tmp);
cnt+=(T[1].Querysum(u)-T[1].Querysum(tmp));
T[1].Add(Ct(a[i],j-1),1);
}else{
cnt+=(T[0].Querysum(u)-T[0].Querysum(tmp));
cnt+=T[1].Querysum(tmp);
T[0].Add(Ct(a[i],j-1),1);
}
if(cnt%2!=0)ans^=(1<<(j-1));
}
}
cout<<ans<<endl;
return 0;
}