Codeforces Round #757 Divan and bitwise operations 题解 (Java/C++)

题解

我们首先考虑如何构造出符合输入的数组A。
不难想到,假设存在这样的i,使得l1<i<r1且l2<i<r2,那么如果对应的x1和x2不等,那么a[i]可以等于x1&x2。
也就是说如果x1或者x2中的某一个二进制位为0,则a[i]在这个二进制位必为0。
于是很自然的,对于任意二进制位,类似于括号配对,我们可以找出必为0的起始和结束位置。进而构造出A。

接着我们考虑怎么根据这个数组A求出结果。

显然,对于任意一个子序列,如果某一个二进制位上为1的数有奇数个,则最后的XOR在这一位上也必为1。否则则为0。
另一方面,在计算最终结果相加时,显然通过十进制数相加或是通过二进制数相加是同样的。

于是,整体上,我们按二进制位进行依次计算。
对于某一个二进制位i(0<i<31)。要使这一位对结果有影响,显然我们只考虑这一位为1的情况。
因此,假设整个数组A中,有a个数在第i位上是1。那么我们就从a个数中选b个数(b必为奇数)出来,然后在为0的数中任意选若干个即可。
因此,对于第i位,其结果为$(1<<i) \cdot\sum\limits_{b \text { is odd}} C_a^b \cdot 2^{n-a}$。也就是$(1<<i) \cdot 2^{n-a} \cdot\sum\limits_{b \text { is odd}} C_a^b$。

代码

Java

Submission #137679484 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #137682160 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论