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

Solution:

We first consider how to construct an array A that matches the input.
It is not difficult to imagine that if there is such an i such that l1<i<r1 and l2<i<r2, then if the corresponding x1 and x2 are not equal, then a[i] can be equal to x1&x2.
That is to say, if one of the binary bit of x1 or x2 is 0, then a[i] must be 0 in this binary bit.
So naturally, for any binary bit, similar to parentheses pairing, we can find the starting and ending positions that must be 0. And then construct A.

Then we consider how to find the result based on this array A.

Obviously, for any subsequence, if there are odd numbers of 1 in a binary bit, the last XOR must also be 1 in this bit. Otherwise, it is 0.
On the other hand, when calculating the addition of the final result, it is obvious that adding through decimal numbers or adding through binary numbers is the same.

Therefore, in general, we perform calculations bit by bit.
For a certain binary bit i (0<i<31). To make this bit have an impact on the result, obviously we only consider the case where this bit is 1.
Therefore, suppose that in the entire array A, the number of 1s is a in the i-th bit. Then we choose b numbers from these 1s (b must be an odd number), and then choose any number of numbers that are 0.
Therefore, for the i-th bit, the result is: $(1<<i) \cdot\sum\limits_{b \text { is odd}} C_a^b \cdot 2^{n-a}$. That is $(1<<i) \cdot 2^{n-a} \cdot\sum\limits_{b \text { is odd}} C_a^b$。

Code:

Java

C++