第一行输入一个 n n,表示这序列的数字个数。
第二行输入 n n个数字 a1,a2,a3 a1,a2,a3... an an,代表这个序列。
0≤a1,a2, 0≤a1,a2,... ,an,0≤a1+a2+ ,an,0≤a1+a2+... +an≤106 +an≤106。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
位运算+树状数组+思路~
先求出前缀和a[i],因为异或运算只与单个二进制位有关,所以我们按位来算,只需20位。
对于一位k,我们线性扫过所有前缀和,对于i,如果i的k位==1,那么只有当j<i && j&(1<<k)!=0 && j%(1<<k)>i%(1<<k)
或者j<i && j&(1<<k)==0 && j%(1<<k)<i%(1<<k)时才能更新答案,所以我们记录两个树状数组,分别维护在i之前的k位为1和0的数的个数,位置由j%(1<<k)决定,就可以更新答案了。
位运算没有加括号……以后要注意啊~
#include<cstdio> int n,a[100001],c[1<<20][2],ans,rev[21]; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();} while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } void add(int u,int v,int k) { for(u++;u<=rev[20];u+=u&(-u)) c[u][k]+=v; } int cal(int u,int k) { int now=0; for(u++;u;u-=u&(-u)) now+=c[u][k]; return now; } int main() { n=read();rev[0]=1; for(int i=1;i<=20;i++) rev[i]=rev[i-1]<<1; for(int i=1;i<=n;i++) a[i]=a[i-1]+read(); for(int k=0;k<20;k++) { int now=0; for(int i=1;i<=n;i++) { int x,y; x=((a[i]&rev[k])!=0);y=a[i]%rev[k]; if(x) now++; now+=cal(rev[k]-1,x)-cal(y,x)+cal(y,x^1); add(y,1,x); } if(now&1) ans|=rev[k]; for(int i=1;i<=n;i++) add(a[i]%rev[k],-1,(a[i]&rev[k])!=0); } printf("%d\n",ans); return 0; }