[Codeforces Round #626 (Div. 2, based on Moscow Open Olympiad in Informatics)] -D. Present
以下说到的 位数 均指二进制位数
按位讨论每对（a[i], a[j]）对答案第i位的贡献
log2(1e7) 上取整 24 位
影响第i位的，只有 0~i 位
当a[i] 位为 1 时，能对 答案第i位贡献 1的 就是 a[j]（第i位位0 且 0~（i-1）位与a[i]相加不进位）或者 （第i位为 1 且 0 ~（i-1）相加进位）
当 a[i] 位为 0 时， a[j] (第i位为 1 且 0 ~ （i- 1）相加不进位)，或者 （第i位为 0，且 0 ~ （i- 1）相加进位 ）
由于复杂度原因，要二分查找，那么我们求i位的时候都要排序，怎么排？b[i] = a[i] % (1 << i + 1) ，排序b即可，
其他细节计数，见代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e7 + 5;
int n, a[maxn], res, b[maxn];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (int i = 0; i <= 24; ++i)
{
int mod = 1 << i + 1, ans = 0;
for (int j = 1; j <= n; ++j) b[j] = a[j] % mod;
sort(b + 1, b + 1 + n);
for (int j = 1; j <= n; ++j)
{
if (b[j] & (1 << i))
{
int l = lower_bound(b + 1 + j, b + 1 + n, (1 << i + 1) - b[j]) - b;
int r = lower_bound(b + 1 + j, b + 1 + n, (1 << i + 1) - (b[j] ^ (1 << i))) - b;
ans += l - j + n - r;
}
else
{
int r = lower_bound(b + 1 + j, b + 1 + n, (1 << i + 1) - b[j]) - b;
int l = lower_bound(b + 1 + j, b + 1 + n, (1 << i) - b[j]) - b;
ans += r - l;
}
}
if (ans & 1) res ^= 1 << i;
}
printf("%d", res);
scanf("%d", &n);
return 0;
}