Codeforces Round #626 DIV2 D. Present(思维)

求两两之间和的异或和,

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
const int MAXN = 1e6+5;
const int MOD= 998244353;
int n;
int a[MAXN],b[MAXN];
int main()
{
    while(~scanf("%d",&n)){
        rep(i,1,n)scanf("%d",&a[i]);
        int ans=0;
        rep(i,0,29){
            int k=1<<(i+1);k--;
            rep(j,1,n){
                b[j]=a[j]&k;
            }
            ll num=0;
            sort(b+1,b+n+1);
            int p=(1<<i);
            rep(j,1,n){
                int p1=lower_bound(b+j+1,b+n+1,p-b[j])-b;
                int p2=upper_bound(b+j+1,b+n+1,(p<<1)-1-b[j])-b;
                num+=p2-p1+1;
                p1=lower_bound(b+j+1,b+n+1,(p<<1)+p-b[j])-b;
                num+=n+1-p1+1;
            }
            if(num&1)ans+=p;
        }
        printf("%d\n",ans);
    }
}