Problem Link:
Difficulty:
Medium
Pre-requisites:
Dynamic Programming
Problem:
Given a sequence of positive integers a[1], a[2], a[3], …, a[N], find how many sequences of nonnegative integers b[1], b[2], b[3], …, b[N] exist such that
-
b[i] <= a[i], and
-
the bitwise xor of the two sequences is equal. That is,
a[1] ^ a[2] ^ … ^ a[N] = b[1] ^ b[2] ^ … ^ b[N].
Explanation:
The most useful thing about the XOR Sum of numbers, is that the different bits behave independently of each other. Thus, whenever we are given a question that asks for a special property of the XOR Sum of numbers, we process the numbers one bit at a time.
Also, in questions where we need to find the number of x[i] <= a[i] satisfying some properties, we start from the largest x[i] and go down. Similarly, here too we will start with the most significant bits of a[i], and then go to the least significant bits.
We first make the following observation:
If a number we are considering (some a[i]) is 2x - 1, then by varying over the values from 0 to 2x - 1, we get all possible values of the xor-sum corresponding to those least significant x bits. Thus, since we have a target of just one particular value, we divide the “total number of such numbers” by 2x.
Let us start from the most significant bit, and try to ensure that that bit in the xorsum is the same as the one we need. Let the number of numbers having the current (say k’th) bit = 1 be M. Denote by c[i], the least k significant bits of a[i]. We need to count the number of numbers we can make b[i] <= c[i], where the xor of the b[i]'s k’th bits = (M % 2) (this is so that it gives the same xor value at this bit). Also, we ensure that atleast one of the i’s whose c[i] value has the k’th bit = 1, has the k’th bit of b[i] set to 0. This is so that the remaining bits can then be chosen arbitrarily, and also because the case where all the bits are counted as 1 will be accounted for in further iterations, where we discard the k’th bit from c[i]'s.
Thus, let us consider the k’th bit as being considered, and let f(i, k, j) = number of ways of choosing numbers b[1], b[2], …, b[i], such that the k’th bit’s xor value of b[1], b[2], …, b[i] = j. Also, we need to keep track of how many numbers of b’s are there such that all the corresponding b[i]'s are set to 1 whenever c[i]'s k’th bit is 1 (call this “one”), and how many numbers of b[i]'s are there when c[i]'s k’th bit is 0 (call this “zero”). This is because we need to exclude such numbers from our final calculation. Finally, we add the quantities (f(N, k, M%2) - one*zero) / 2k to our answer, and carry on (you may like to see this answer for further clarification after reading the below pseudocode).
Pseudocode follows:
// given initially c[i] = a[i]
for k = 29 to 0
F[0][k][0] = 1, F[0][k][1] = 0
one = 1, zero = 1
M = 0
for i = 1 to N
if( (c[i] & (2<sup>k</sup>)) > 0)
M++
c[i] -= 2<sup>k</sup>
one = one * (c[i]+1)
f(i, k, 1) = f(i-1, k, 1) * 2<sup>k</sup> + f(i-1, k, 0) * (c[i]+1)
f(i, k, 0) = f(i-1, k, 0) * 2<sup>k</sup> + f(i-1, k, 1) * (c[i]+1)
//the above two are because of considering the case where we set the k'th bit of b[i] to 0 - which gives us 2<sup>k</sup> numbers, or we set it to 1, which gives us numbers 0 to c[i] (i.e. c[i]+1 numbers in total)
else
zero = zero * (c[i]+1)
f(i, k, 1) = f(i-1, k, 1) * (c[i]+1)
f(i, k, 0) = f(i-1, k, 0) * (c[i]+1)
ans += (f(N, k, M%2) - one * zero)/2<sup>k</sup>
output ans + 1 // the +1 corresponds to the case where all bits of b match all bits of a
NOTE: While dividing by 2k, we should do the division as multiplication by inverse modulo prime 1000000009, as are all the multiplications etc.
Setter’s Solution:
Can be found here
Tester’s Solution:
Can be found here
to be a state of computation where you are counting b[i]'s whose (k+1, k+2, …, 29)'th bits all match that of a[i]'s.