codeforces1323D Present

题意

求 $(a_{1} + a_{2}) \oplus (a_{1} + a_{3}) \oplus \dots \oplus (a_{1} + a_{n}) \oplus (a_{2} + a_{3}) \oplus \dots \oplus (a_{2} + a_{n}) \dots \oplus (a_{n - 1} + a_{n})$

其中 $n \leq 400000$ ， $a_{i} \leq 1 0^{7}$

分析

这场用手速上了紫嘿嘿嘿，不过 $D$ 没做出来还是太菜了。
对于这种二进制的题，都是一位一位考虑。这里考虑答案的第 $k$ 位。
我们将每个数取前 $k$ 位。现在就是考虑 $a_{i} + a_{j}$ 第 $k$ 位为 $1$ 的对数。
第 $k$ 位为 $1$ 只有两种情况：

第 $k$ 位为 $1$ ，第 $k + 1$ 位为 $0$
这种情况就是大于 $2^{k} - a_{i}$ 的个数减去大于 $2^{k + 1} - a_{i}$ 的个数
第 $k$ 位和第 $k + 1$ 位都为 $1$
这种情况就是大于 $2^{k} + 2^{k + 1} - a_{i}$ 的 $a_{j}$ 个数

加起来就是第 $k$ 位为 $1$ 的对数了。
二分找个数复杂度 $O (l o g n)$
总共 26 位
复杂度 $O (26 n l o g n)$

代码如下

#include <bits/stdc++.h>
#define N 400005
using namespace std;
int a[N], b[N], n;
int get(int l, int x){
	if(b[n] < x) return 0;
	int r = n, mid;
	while(l < r){
		mid = l + r >> 1;
		if(b[mid] >= x) r = mid;
		else l = mid + 1;
	}
	return n - l + 1;
}
int main(){
	int i, j, m, sum, ans = 0;
	scanf("%d", &n);
	for(i = 1; i <= n; i++) scanf("%d", &a[i]);
	for(j = 0; j <= 26; j++){
		for(i = 1; i <= n; i++) b[i] = a[i] & ((1 << j + 1) - 1);
		//printf("%d======\n", j);
		//for(i = 1; i <= n; i++) printf("%d ", b[i]);
		//printf("\n");
		sort(b + 1, b + i);
		sum = 0;
		for(i = 1; i < n; i++){
			sum = (sum + get(i + 1, (1 << j) - b[i])) % 2;
			sum = (sum - get(i + 1, (1 << j + 1) - b[i])) % 2;
			sum = (sum + get(i + 1, (1 << j) + (1 << j + 1) - b[i])) % 2;
		}
		//printf("sum === %d\n", sum);
		if(sum % 2) ans |= (1 << j);
	}
	printf("%d", ans);
	return 0;
}