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 black square. Unfolding a move produces 4 possible locations for the original square(s). Thus the number of possible original black squares after undoing M moves is 4^M. The number of ways to select a non-empty subset of these 4^M squares is 2^{4^M}-1. Let B be the number of black squares in the original grid. Thus our final formula is (2^{4^M}-1)^B.

To compute 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), by using exponentiation by squaring to quickly compute the exponents.


  • 0
    Plasmatic  commented on March 8, 2020, 6:15 p.m.

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

    • 4
      aeternalis1  commented on March 8, 2020, 6:34 p.m. edited

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