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} \bmod (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)$ .

Time Complexity: $\mathcal O(4^K + \log M + \log \alpha + \log B)$ , where $\alpha = 4^M \bmod (10^9 + 6)$ ~\alpha = 4^M \bmod (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 \pmod 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} \pmod{10^9+7}~, notice $2^{4^M} = 2^k \cdot \left(2^{q-1}\right)^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 \pmod{10^9+7}~, we know $2^{4^M} \equiv 2^k \pmod{10^9+7}$ ~2^{4^M} \equiv 2^k \pmod{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~.