Contest Duration: - (local time) (120 minutes) Back to Home
Official

## C - XOR to All Editorial by evima

In this editorial, let $$A$$ and $$B$$ denote the sequence before and after the operations, respectively.

### [1] Characterization of the sequence after the operations

For $$B$$, the sequence after the operations, the following holds:

• $$A_i\oplus A_j = B_i\oplus B_j$$ for every $$i, j$$.
• If at least one operation is done, $$B_i = 0$$ for some $$i$$.

The former property can be seen from the fact that $$a\oplus b = (a\oplus x) \oplus (b\oplus x)$$ for any non-negative integers $$a, b, x$$. The former property can be seen from the fact that, if at least one operation is done, the term that was equal to the last chosen $$x$$ becomes $$0$$.

From these properties, the sequence after the operations, $$B$$, must be one of the following.

• The same sequence as the sequence $$A$$ before the operation (when doing zero operations).
• A sequence determined by $$B_i = A_i\oplus A_k$$ ($$1\leq i\leq N$$) for some $$k$$.

On the other hand, these sequences can be obtained as the sequence $$B$$ after the operations (by doing zero or one operation).

Now we have determined all possible variants of the sequence $$B$$ after the operations. If we can compute $$\sum_{i=1}^N B_i$$ for all of them, we can find the answer.

Thus, for each $$x\in \{0, A_1, \ldots, A_N\}$$, we want to compute $$\sum_{i=1}^N (A_i\oplus x)$$. Let us choose $$K$$ so that $$\max_i A_i < 2^K$$ and do the computations as follows.

• For each $$k (0\leq k < K)$$, compute the sum of the digits of $$(A_i\oplus x)$$ in $$2^k$$’s place.
• Sum up the results.

This can be done as follows, in the following complexity.

• For each $$k$$, precompute the numbers of $$0$$s and $$1$$s among the digits of $$A_i$$ in $$2^k$$’s place (in $$\Theta(NK)$$ time).
• Use these counts to compute $$\sum_{i} (A_i\oplus x)$$ for each $$x$$ (in $$\Theta(K)$$ time for each $$x$$, for a total of $$\Theta(NK)$$ time).

Summing up the above, the problem can be solved in $$\Theta(NK)$$ time.

posted:
last update: