Editorial for GlobeX Cup '18 S3 - Playing With Bits

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Ninjaclasher

For the first subtask, we can brute force all possible combinations of the array $a$ $a$ , and check if they match the constraints.

Time Complexity: $\mathcal O(2^{KN})$ $O (2^{K N})$

For the rest of the subtasks (in general), we need to improve the time complexity.

Let us look at the xor operation first. A bit $i$ $i$ in $V$ $V$ is set if and only if there is an odd number of $a_j$ $a_{j}$ s with the $i^{th}$ $i^{t h}$ bit set. A bit $i$ $i$ in $V$ $V$ is not set if there is an even number of $a_j$ $a_{j}$ s with the $i^{th}$ $i^{t h}$ bit set. Thus, we need to look at each bit in $V$ $V$ individually. If the $i^{th}$ $i^{t h}$ bit is set, we need to calculate the number of ways to place an odd number of set bits in the array $a$ $a$ of size $N$ $N$ . Thus, $\binom N {\text{odd}}$ $(\binom{N}{odd})$ ( $N$ $N$ choose an odd number). If the $i^{th}$ $i^{t h}$ bit is not set, we need to calculate the number of ways to place an even number of set bits in the array $a$ $a$ of size $N$ $N$ . Thus, $\binom N {\text{even}}$ $(\binom{N}{even})$ ( $N$ $N$ choose an even number).

For the or operation, the $i^{th}$ $i^{t h}$ bit in $V$ $V$ is set if any of $a_j$ $a_{j}$ has set bit $i$ $i$ . An $i^{th}$ $i^{t h}$ bit in $V$ $V$ is unset if all of $a_j$ $a_{j}$ has an unset bit $i$ $i$ . Similar to the xor operation, we must loop through each bit. There are $2^N-1$ $2^{N} - 1$ ways to choose a combination for the $N$ $N$ elements, such that at least one of them has a set bit $i$ $i$ , and there is exactly $1$ $1$ way to choose a combination for the $N$ $N$ elements, such that all bit $i$ $i$ s are unset.

The and operation can be handled in the same manner as the or operation, and so we will leave it as an exercise for the reader.

With this, we can go through each bit $i$ $i$ up to $K$ $K$ , and multiply the number of ways for each bit accordingly. Be wary to modulo to prevent overflow.

It is trivial to calculate $2^N-1$ $2^{N} - 1$ with Exponentiation By Squaring. To calculate $\binom N {\text{even}}$ $(\binom{N}{even})$ and $\binom N {\text{odd}}$ $(\binom{N}{odd})$ quickly requires a little more mathematical insight (which are the next 3 subtasks).

For the second subtask, we can precompute by looping up to $N$ $N$ ( $0$ $0$ to $N$ $N$ inclusive), and calculate $\binom N i$ $(\binom{N}{i})$ . Multiply all even $i$ $i$ into a final variable, and all odd $i$ $i$ into another variable. Note that we need to use modular division in order to prevent overflow. Noticing that $M$ $M$ is a prime, we can use Fermat's Little Theorem to calculate the modular multiplicative inverse, and perform modular division accordingly (by multiplying by the modular multiplicative inverse).

Time Complexity: $\mathcal O(N + K)$ $O (N + K)$

For the third subtask, we notice that $M$ $M$ is not a prime. Instead of performing modular division in order to compute $\binom N i$ $(\binom{N}{i})$ , we need an alternative. We can use a segment tree or balanced binary search tree (similar to this problem) that stores the prime factors. When moving from $\binom N i$ $(\binom{N}{i})$ to $\binom N {i+1}$ $(\binom{N}{i + 1})$ , we need to remove some prime factors, and add some. For more details, refer to the editorial from that problem.

Time Complexity: $\mathcal O(N \log^2 N + K)$ $O (N \log^{2} N + K)$ or better

For the last subtask, $N \le 10^9$ $N \leq 10^{9}$ , meaning that even $\mathcal O(N)$ $O (N)$ is too slow. We need a sublinear algorithm. With some mathematical insight, we can show that $\binom N {\text{odd}} = \binom N {\text{even}} = 2^{N-1}$ $(\binom{N}{odd}) = (\binom{N}{even}) = 2^{N - 1}$ (If you want a formal proof, open a ticket by clicking the "Report an issue" button at the bottom of the problem description). Thus, we can use Exponentiation By Squaring to precompute the values needed for the xor operation as well.

Time Complexity: $\mathcal O(\log N + K)$ $O (\log N + K)$

Comments

There are no comments at the moment.