CF1322B Present 题解
题目链接：CF1322B Present
题意：
给出一个长度为 \(n\) 的数列 \(a\)。其中第 \(i\) 项为 \(a_i\)。
请你求出 \(\bigoplus_{i=1}^{n}\bigoplus_{j=i+1}^{n}(a_i+a_j)\)。其中 \(\oplus\) 表示按位异或操作。
\(2 \leq n \leq 4 \times 10^5\)，\(1 \leq a_i \leq 10^7\)。
输入格式：
The first line contains a single integer \(n\) — the number of integers in the array.
The second line contains integers \(a_1, a_2, \ldots, a_n\) .
输出格式：
Print a single integer — xor of all pairwise sums of integers in the given array.
注意到 \(a_i \le 10^7\) ，因此二进制的位数 \(\in [0, 25]\)，于是依次考虑每一位的贡献。
显然，如果我们要计算两个数的和的第 \(i\) 位是否为 \(1\) ，至少需要这两个数前 \(i\) 位的信息
不妨预处理出每个数 \(a_j\) 在 \(i\) 相同时前 \(i\) 位所对应的数，记为 \(b_j\) 。
如果 \(b_x+b_y\) 的第 \(i\) 位为 \(1\) ，则
- 第 \(i\) 位没有进位，则 \(b_x + b_y \in [2^i,~2^{i+1}-1]\) 。
- 第 \(i\) 位进位了，但第 \(i-1\) 位也进位了，则 \(b_x + b_y \in [2^{i+1} + 2^i,~(2^{i+1}-1)\times 2]\) 。
那么知道这个范围有什么用处呢？
通常我们要数有多少个数在区间 \([l,r]\) 内，我们可以用 \([1,r]\) 的答案减去 \([1,l)\) 的答案。
于是，对于一个固定的 \(b_x\) ，我们只需要找到有多少个 \(b_y\) 满足 \(b_x + b_y\) 小于等于某个数
可以发现，当 \(b\) 内的每个数都从小到大排序时，我们倒序枚举 \(b_x\) ，那么 \(b_y\) 可以用一个指针来线性维护
不过最后我们要的答案是他们的异或值，不是个数，这个显然可以通过数目的奇偶性判断。
时间复杂度 \(\mathcal{O}(n \log V)\)
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(4e5 + 15))
int n, res, a[N], b[N];
bool check(int x, int y)
{
if(x > y) return 0;
int num = 0;
for(int i = n, l = 1, r = 1; i; i--)
{
while(l <= n && b[i] + b[l] < x) ++l;
while(r <= n && b[i] + b[r] <= y) ++r;
num += r - l - (l <= i && i < r);
}
return (num >> 1) & 1;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 0; i <= 25; i++)
{
for(int j = 1; j <= n; j++) b[j] = a[j] & ((1 << (i + 1)) - 1);
sort(b + 1, b + 1 + n);
int tmp = check(1 << i, (1 << (i + 1)) - 1) ^ check(3 << i, (1 << (i + 2)) - 2);
res += tmp * (1 << i);
}
cout << res << '\n';
return 0;
}参考文献：
