CF1322B Present

逐位考虑，两个数的和在第 $k$ 位为 $1$ 的条件为 $2 ^ k <= a + b < 2 ^ {k + 1}$ （不进位）或者 $a + b \ge 2 ^ {k + 1} + 2 ^ k$ （进位后再满足条件）。记 $calc _ i$ 表示大于等于 $i$ 的数对数量，那么答案可以表示为 $calc _ {2 ^ {k + 1}} - calc _ {2 ^ k} + calc _ {2 ^ {k + 1} + 2 ^ k}$ 。计算时排序后双指针即可统计答案。

查看代码

#include <cstdio>
#include <algorithm>
using namespace std;
template <class Type>
void read (Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write (Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar('0' + x % 10);
}
const int N = 4e5 + 10, M = 25;
int n, w[N], v[N];
bool calc (int k)
{
    bool res = 0;
    for (int r = n, l = 1; l <= r; r--)
    {
        while (w[l] + w[r] < k && l < r)
            l++;
        res ^= r - l & 1;
    }
    return res;
}
int main ()
{
    read(n);
    for (int i = 1; i <= n; i++)
        read(v[i]);
    int res = 0;
    for (int i = 0; i < M; i++)
    {
        for (int j = 1; j <= n; j++)
            w[j] = v[j] & (1 << i + 1) - 1;
        sort(w + 1, w + n + 1);
        res |= (calc(1 << i) ^ calc(1 << i + 1) ^ calc((1 << i + 1) + (1 << i))) << i;
    }
    write(res);
    return 0;
}