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 4M. The number of ways to select a non-empty subset of these 4M squares is 24M1. Let B be the number of black squares in the original grid. Thus our final formula is (24M1)B.

To compute 24Mmod(109+7), we can apply Fermat's Little Theorem, to get 24Mmod(109+7)2(4Mmod(109+6))mod(109+7).

Time Complexity: O(4K+logM+logα+logB), where α=4Mmod(109+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 109+6 instead of 109+7 for 4M?


    • 4
      aeternalis1  commented on March 8, 2020, 10:34 p.m. edit 2

      Notice FLT shows us that pq11(modq) for prime q where p is coprime to q. In this problem we have p=2 and q=109+7. Since we wish to find 24M(mod109+7), notice 24M=2k(2q1)m for some m,k, and since we know 2q11(mod109+7), we know 24M2k(mod109+7), so it boils down to finding the m,k such that 4M=(q1)m+k, where q1=109+6, and this is where you'd use your normal mod operator to find the remainder k.