灵茶八题
其中有一道前置题目 ARC092D
题解为
二进制题目，常用技巧之一是拆位，但这只能用于各个比特位互相独立的情况。
本题加法有进位，破坏了这种独立性，这要如何处理呢？
其实也可以拆位（我叫它加法拆位）。
按照 mod (2^k) 拆位，例如要计算从低到高第三个比特位，可以 mod 8（即 AND 7）。
记 s = a[i]%8 + b[j]%8。
要想知道这 n^2 个 s 中，从低到高第三个比特位有多少个 1，相当于求满足下式的 s 的个数：
100 <= s <= 111 或 1100 <= s <= 1111（数字为二进制）。
这可以在按照 mod 8 排序后，用五个指针做。一个指针遍历 a[i]，另外 4 个指针在 b 上，对应着上式的 4 个区间端点。
注意：相加可能会进位到第 29 个比特位，在枚举的时候请注意上界。
优化：
注意到 s <= 1<<(k+2)-1 是恒成立的，上面代码中的 q 恒等于 n-1。
而 n 个 n-1 的异或和一定是偶数（最低位一定是 0），所以可以完全去掉 q。
参考代码
cpp
for (int k = 0; k < 29; k++)
{
int msk = (1 << (k + 1)) - 1;
sort(a, a + n, [&](int x, int y) {return (x & msk) < (y & msk);});
sort(b, b + n, [&](int x, int y) {return (x & msk) < (y & msk);});
int cnt = 0;
int i = n - 1, j = n - 1, p = n - 1, q = n - 1;
int l1 = 1 << k, r1 = (1 << (k + 1)) - 1, l2 = 3 << k, r2 = (1 << (k + 2)) - 1;
for (int t = 0; t < n; t++)
{
int v = a[t];
while (i >= 0 && (v & msk) + (b[i] & msk) >= l1) i --;
while (j >= 0 && (v & msk) + (b[j] & msk) > r1) j --;
while (p >= 0 && (v & msk) + (b[p] & msk) >= l2) p --;
while (q >= 0 && (v & msk) + (b[q] & msk) > r2) q --;
cnt += j - i + q - p;
}
res |= (cnt & 1) << k;
}TODO：CF1322B