题目链接：Codeforces 1148F

你有 $n$ 个物品，每个物品有两个属性 $val_i$ 和 $mask_i$。保证最初 $val_i$ 的和非零。

你想要选择一个正整数 $s$ 并将所有物品的 $val_i$ 进行修改，第 $i$ 个物品的 $val_i$ 通过如下方法修改：

• 将 $mask_i$ 和 $s$ 在二进制下考虑。
• 计算 $s\ \text{AND}\ mask_i$ 的值。
• 如果 $s\ \text{AND}\ mask_i$ 的值中有奇数个 $1$，那么将 $val_i$ 替换为 $-val_i$；否则不进行修改。

你需要找到这样一个整数 $s$，使得所有物品 $val_i$ 的和相对最初的和正负号相反（不允许为 $0$）。但是和的绝对值可以是任意的。

数据范围：$1 \le n \le 3 \times 10 ^ 5$，$-10 ^ 9 \le val_i \le 10 ^ 9$，$1 \le mask_i, s < 2 ^ {62}$。

Solution

我们考虑用数学归纳法，归纳得到 $1 \le mask_i, s < 2 ^ K$ 时的答案。

边界条件为 $K = 1$，此时 $s = 1$ 即可。

加入我们已经处理好了 $2 ^ K$ 的答案 $s'$，那么考虑 $\forall 2 ^ K \le val_i < 2 ^ {K + 1}$ 必有 $val_i\ \text{AND}\ 2 ^ K \ne 0$。那么答案的第 $K$ 位为 $1$ 当且仅当：$s = s' + 2 ^ K$ 时，这些 $val_i$ 的贡献和（根据 $mask_i\ \text{AND}\ s$ 的 $1$ 的个数判断贡献的正负）与最初的和正负号相反。

上面说的有点拗口，具体实现详见代码。

吐槽：编译器内置的 __builtin_popcount 竟然不支持 long long，需要使用 __builtin_popcountll！

时间复杂度：$\mathcal O(n \log mask_i)$。

Code

#include <cstdio>

const int N = 3e5 + 5;

int n, v[N];
long long s[N];

int main() {
    scanf("%d", &n);
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d%lld", &v[i], &s[i]);
        sum += v[i];
    }
    if (sum < 0) {
        for (int i = 1; i <= n; i++) v[i] *= -1;
    }
    long long ans = 0;
    for (int k = 0; k < 62; k++) {
        long long sum = 0;
        for (int i = 1; i <= n; i++) {
            if ((1LL << k) <= s[i] && s[i] < (1LL << (k + 1))) {
                sum += ((__builtin_popcountll(ans & s[i]) & 1) ? v[i] : -v[i]);
            }
        }
        if (sum < 0) ans |= (1LL << k);
    }
    printf("%lld\n", ans);
    return 0;
}