Розбір
Problem Author: | Oleksandr Tymkovych |
Editorial by: | Oleksandr Tymkovych |
Let's solve the problem for one query , when all the friends attend the party.
We may consider each bit independently, so if we solve the problem for then we can also solve for arbitrary .
Now, let's work with the formula:
We know that only if the number of ones among is odd. We are not interested when that term equals zero, since it contributes nothing to our total sum.
Let denote the number of ones in our array.
The formula simplifies to
since we choose which ones will be before and which ones will be after . Also, we multiply by factorials, since the ones and zeroes are indistinguishable, so we can permute them as we wish.
Hence, the formula depends on and . The number of ones on the segment may be pre-calculated with partial sums.
In () we used the Chu-Vandermonde identity:
Proof: imagine a binary sequence of length with exactly ones (the right part counts the number of such sequences). To show a bijection with the left part, consider the -th one
in the -th position in the sequence.