time limit per test3 seconds
memory limit per test512 megabytes
inputstandard input
outputstandard output

Catherine received an array of integers as a gift for March 8. Eventually she grew bored with it, and she started calculated various useless characteristics for it. She succeeded to do it for each one she came up with. But when she came up with another one — xor of all pairwise sums of elements in the array, she realized that she couldn’t compute it for a very large array, thus she asked for your help. Can you do it? Formally, you need to compute

(a1+a2)⊕(a1+a3)⊕…⊕(a1+an)
⊕(a2+a3)⊕…⊕(a2+an)
…⊕(an−1+an)

Here x⊕y is a bitwise XOR operation (i.e. x ^ y in many modern programming languages). You can read about it in Wikipedia: https://en.wikipedia.org/wiki/Exclusive_or#Bitwise_operation.

Input
The first line contains a single integer n (2≤n≤400000) — the number of integers in the array.

The second line contains integers a1,a2,…,an (1≤ai≤107).

Output
Print a single integer — xor of all pairwise sums of integers in the given array.

Examples
inputCopy
2
1 2
outputCopy
3
inputCopy
3
1 2 3
outputCopy
2
Note
In the first sample case there is only one sum 1+2=3.

In the second sample case there are three sums: 1+2=3, 1+3=4, 2+3=5. In binary they are represented as 0112⊕1002⊕1012=0102, thus the answer is 2.

⊕ is the bitwise xor operation. To define x⊕y, consider binary representations of integers x and y. We put the i-th bit of the result to be 1 when exactly one of the i-th bits of x and y is 1. Otherwise, the i-th bit of the result is put to be 0. For example, 01012⊕00112=01102.

今天这一场大概是手速场的div2，体会到了和大佬们的差距。
真实太菜了，要好好做题了，这样下去也不知道哪年能拿金。

先来说题，这个题的题意就是给定一个数列，两两求和然后再异或求和。
做法是单独考虑每一位，考虑当前位 1 的个数。
因为加和会产生进位的影响，所以我们要把 每个数 k 位以下全部取出来，然后从小到大排序，利用单调性O（n） 处理这一位的贡献。
处理的时候考虑不进位 1 和进位之后的 1 。

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<vector>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#define ll long long
#define llu unsigned ll
#define pr make_pair
#define pb push_back
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=400100;
int a[maxn],b[maxn];
int main(void)
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    int ans=0;
    for(int k=0;k<=24;k++)
    {
        int now=(1<<(k+1))-1;
        int res=(1<<k);
        for(int i=1;i<=n;i++)
            b[i]=a[i]&now;
        sort(b+1,b+n+1);

        int pos[4]={0,1,1,1},cnt=0;
        for(int i=n;i>=1;i--)
        {
            for(int j=1;j<=3;j++)
                while(pos[j]<=n&&b[pos[j]]+b[i]<j*res) pos[j]++;
            cnt+=max(0,min(i,pos[2])-pos[1]);
            cnt+=max(0,i-pos[3]);
        }
        if(cnt&1) ans|=(1<<k);
    }
    printf("%d\n",ans);
    return 0;
}