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

C++