题意
求对所有的二元组$(i,j)(i<j)$,$a_i+a_j$的异或和
分析
考虑对于第$k$位的贡献,将所有数对$2^{k+1}$取模(因为大于等于$2^{k+1}$的部分对第$k$位不产生贡献)
对于任意$a_i$和$a_j$来说,和要在第$k$位为$1$(为$0$不产生贡献),即和的范围必须在$[2^k,2^{k+1}-1]$或$[2^k+2^{k+1},2^{k+2}-2]$中
如果产生的贡献为奇数,则答案中该位为$1$,否则为$0$
统计第$k$位时,则可以取模,排序,双指针(二分),分别统计两个区间内的数,合并
1 |
|