cf1322BPresent
首先拆位是显然的，对于两个数a[i],a[j]，除了考虑当前位上的数，我们还要考虑是否会产生进位，我们可以利用基数排序+双指针，因为我们每次都是将低位的排好序了，所以我们可以用双指针计算进位，然后分类计算一下，当前为为1的情况即可。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<ctime>
#include<unordered_map>
#include<queue>
#define A puts("YES")
#define B puts("NO")
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc (o<<1|1)
#define bit ((a[i]>>id)&1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
const ll mo=1e9+7;
const int N=4e5+5;
int b[31],n,a[N],c[N],cnt[2],now,ans;
int t[N][2];
int s1,s2;
bool pd(int x,int y,int d){
s1=x&(b[d]-1);
s2=y&(b[d]-1);
return s1+s2>=b[d];
}
int main()
{
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
b[0]=1;
fo(i,1,30) b[i]=b[i-1]*2;
scanf("%d",&n);
fo(i,1,n) scanf("%d",&a[i]);
fo(id,0,30) {
now=0;
memset(cnt,0,sizeof(cnt));
memset(t,0,sizeof(t));
fo(i,1,n) cnt[bit]++;
if (!id) {
now+=(cnt[0]&1)*(cnt[1]&1);
}
else{
fd(i,n,1) {
fo(j,0,1) t[i][j]=t[i+1][j];
t[i][bit]++;
}
int r=n;
fo(i,1,n-1) {
r=max(i+1,r);
while (r>i+1 && pd(a[r-1],a[i],id)) r--;
if (pd(a[r],a[i],id)) {
now+=t[r][bit];
now+=t[i+1][bit^1]-t[r][bit^1];
}
else {
now+=t[i+1][bit^1];
}
now&=1;
}
}
cnt[1]+=cnt[0];
fd(i,n,1) c[cnt[bit]--]=a[i];
fo(i,1,n) a[i]=c[i];
if (now&1) ans+=b[id];
}
printf("%d",ans);
return 0;
}