题解 CF1322B 【Present】
xht
2020-03-09 23:31:44
按位考虑。
对于第 $k$ 位，我们只关心每个数对 $2^{k+1}$ 取模后的值。
对于两个取模后的数，如果要在第 $k$ 位为 $1$，和必须在 $[2^k, 2^{k+1}-1]$ 或 $[2^k + 2^{k+1}, 2^{k+2}-2]$ 中。
排序之后双指针扫一遍即可，时间复杂度 $\mathcal O(n \log n \log w)$。
```cpp
const int N = 4e5 + 7;
int n, a[N], b[N], ans;
inline bool calc(int L, int R) {
if (L > R) return 0;
ll ret = 0;
for (int i = n, l = 1, r = 1; i; i--) {
while (l <= n && b[i] + b[l] < L) ++l;
while (r <= n && b[i] + b[r] <= R) ++r;
ret += r - l - (l <= i && i < r);
}
return (ret >> 1) & 1;
}
inline bool solve(int k) {
for (int i = 1; i <= n; i++) b[i] = a[i] & ((1 << (k + 1)) - 1);
sort(b + 1, b + n + 1);
return calc(1 << k, (1 << (k + 1)) - 1) ^ calc(3 << k, (1 << (k + 2)) - 2);
}
int main() {
rd(n), rda(a, n);
for (int i = 0; i < 26; i++) ans |= solve(i) << i;
print(ans);
return 0;
}
```