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)$(a1​+a2​)⊕(a1​+a3​)⊕…⊕(a1​+an​)⊕(a2​+a3​)⊕…⊕(a2​+an​)…⊕(an−1​+an​)

其中 $n\le 400000$n≤400000， $a_i\le 10^7$ai​≤107

分析

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

• 第 $k$k 位为 $1$1，第 $k+1$k+1 位为 $0$0
  这种情况就是大于 $2^k-a_i$2k−ai​ 的个数减去大于 $2^{k+1}-a_i$2k+1−ai​ 的个数
• 第 $k$k 位和第 $k+1$k+1 位都为 $1$1
  这种情况就是大于 $2^k+2^{k+1}-a_i$2k+2k+1−ai​ 的 $a_j$aj​ 个数

加起来就是第 $k$k 位为 $1$1 的对数了。
二分找个数复杂度 $O\left(logn\right)$O(logn)
总共 26 位
复杂度 $O\left(26nlogn\right)$O(26nlogn)

代码如下

#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;
}