codeforces1323D Present

题意

求 $$\begin{gathered} (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) \end{gathered}$$

其中 $n\le 400000$，$a_i\le 10^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(logn)$
总共 26 位
复杂度 $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 === %dn", sum);
if(sum % 2) ans |= (1 << j);
}
printf("%d", ans);
return 0;
}

最后

以上就是雪白星月为你收集整理的codeforces1323D Present的全部内容，希望文章能够帮你解决codeforces1323D Present所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。