Redaksiya

Problem Author:	Oleksandr Tymkovych
Editorial by:	Oleksandr Tymkovych

Let's solve the problem for one query $l = 1, r = n$ , when all the friends attend the party.

We may consider each bit independently, so if we solve the problem for $a_{i} \in {0, 1}$ then we can also solve for arbitrary $a_{i}$ .

Now, let's work with the formula:

p \in S_{n} \sum k = 1 \sum n (a [p_{1}] \oplus a [p_{2}] \oplus \dots \oplus a [p_{k}]) = k = 1 \sum n p \in S_{n} \sum (a [p_{1}] \oplus a [p_{2}] \oplus \dots \oplus a [p_{k}])

We know that $a [p_{1}] \oplus a [p_{2}] \oplus \dots \oplus a [p_{k}] = 1$ only if the number of ones among $a [p_{1}], \dots, a [p_{k}]$ is odd. We are not interested when that term equals zero, since it contributes nothing to our total sum.

Let $cnt$ denote the number of ones in our array.

The formula simplifies to

answer = k = 1 \sum n x = 0 \sum ⌊ \frac{cnt - 1}{2} ⌋ [(2 x + 1 k) \cdot (cnt - ( 2 x + 1 ) n - k) \cdot cnt! \cdot (n - cnt)!]

since we choose which ones will be before $k$ and which ones will be after $k$ . Also, we multiply by factorials, since the ones and zeroes are indistinguishable, so we can permute them as we wish.

answer = cnt! \cdot (n - cnt)! k = 1 \sum n x = 0 \sum ⌊ \frac{cnt - 1}{2} ⌋ [(2 x + 1 k) \cdot (cnt - ( 2 x + 1 ) n - k)]

= cnt! \cdot (n - cnt)! x = 0 \sum ⌊ \frac{cnt - 1}{2} ⌋ k = 1 \sum n [(2 x + 1 k) \cdot (cnt - ( 2 x + 1 ) n - k)]

= cnt! \cdot (n - cnt)! x = 0 \sum ⌊ \frac{cnt - 1}{2} ⌋ (cnt + 1 n + 1) (*)

= cnt! \cdot (n - cnt)! \cdot ⌈ \frac{cnt}{2} ⌉ \cdot (cnt + 1 n + 1)

= cnt! \cdot (n - cnt)! \cdot ⌈ \frac{cnt}{2} ⌉ \cdot \frac{( n + 1 )!}{( cnt + 1 )! \cdot ( n - cnt )!}

= ⌈ \frac{cnt}{2} ⌉ \cdot \frac{( n + 1 )!}{cnt + 1}

Hence, the formula depends on $cnt$ and $n$ . The number of ones on the segment may be pre-calculated with partial sums.

In ( $*$ ) we used the Chu-Vandermonde identity: $m = 0 \sum n (j m) (k - j n - m) = (k + 1 n + 1) .$

Proof: imagine a binary sequence of length $n + 1$ with exactly $k + 1$ ones (the right part counts the number of such sequences). To show a bijection with the left part, consider the $(j + 1)$ -th one in the $(m + 1)$ -th position in the sequence.