Editorial for DMPG '17 S3 - Black and White III - Olympiads Online Judge

Editorial for DMPG '17 S3 - Black and White III

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: Kirito

Let us consider first the case where there is only $1$ $1$ black square. Unfolding a move produces $4$ $4$ possible locations for the original square(s). Thus the number of possible original black squares after undoing $M$ $M$ moves is $4^M$ $4^{M}$ . The number of ways to select a non-empty subset of these $4^M$ $4^{M}$ squares is $2^{4^M}-1$ $2^{4^{M}} - 1$ . Let $B$ $B$ be the number of black squares in the original grid. Thus our final formula is $(2^{4^M}-1)^B$ $(2^{4^{M}} - 1)^{B}$ .

To compute $2^{4^M} \bmod (10^9+7)$ $2^{4^{M}} mod (10^{9} + 7)$ , we can apply Fermat's Little Theorem, to get $2^{4^M} \bmod (10^9+7) \equiv 2^{\left(4^M \bmod (10^9 + 6)\right)} \bmod (10^9+7)$ $2^{4^{M}} mod (10^{9} + 7) \equiv 2^{(4^{M} mod (10^{9} + 6))} mod (10^{9} + 7)$ .

Time Complexity: $\mathcal O(4^K + \log M + \log \alpha + \log B)$ $O (4^{K} + \log M + \log α + \log B)$ , where $\alpha = 4^M \bmod (10^9 + 6)$ $α = 4^{M} mod (10^{9} + 6)$ , by using exponentiation by squaring to quickly compute the exponents.

Comments

0

Plasmatic commented on March 8, 2020, 10:15 p.m.

Why is the mod $10^9+6$ $10^{9} + 6$ instead of $10^9+7$ $10^{9} + 7$ for $4^M$ $4^{M}$ ?

4

aeternalis1 commented on March 8, 2020, 10:34 p.m. ← edit 2 →

Notice FLT shows us that $p^{q-1} \equiv 1 \pmod q$ $p^{q - 1} \equiv 1 (\mod q)$ for prime $q$ $q$ where $p$ $p$ is coprime to $q$ $q$ . In this problem we have $p = 2$ $p = 2$ and $q = 10^9+7$ $q = 10^{9} + 7$ . Since we wish to find $2^{4^M} \pmod{10^9+7}$ $2^{4^{M}} (\mod 10^{9} + 7)$ , notice $2^{4^M} = 2^k \cdot \left(2^{q-1}\right)^m$ $2^{4^{M}} = 2^{k} \cdot {(2^{q - 1})}^{m}$ for some $m, k$ $m, k$ , and since we know $2^{q-1} \equiv 1 \pmod{10^9+7}$ $2^{q - 1} \equiv 1 (\mod 10^{9} + 7)$ , we know $2^{4^M} \equiv 2^k \pmod{10^9+7}$ $2^{4^{M}} \equiv 2^{k} (\mod 10^{9} + 7)$ , so it boils down to finding the $m, k$ $m, k$ such that $4^M = (q-1)m + k$ $4^{M} = (q - 1) m + k$ , where $q-1 = 10^9+6$ $q - 1 = 10^{9} + 6$ , and this is where you'd use your normal mod operator to find the remainder $k$ $k$ .