PROBLEM LINK:
Author: Aman Kumar Gupta
Editorialist: Aman Kumar Gupta
DIFFICULTY:
EASY-MEDIUM.
PREREQUISITES:
DP, Math, Matrix, Fast exponentiation.
PROBLEM:
The number of ways you can mine a row of size 1 * n using given types of bombs modulo 10^9+7.
EXPLANATION:
The first method which can be used is DP of course. It seems to be a classical DP problem.
So when the size of the row is 1 * 1, dp[1] = 0. When the size of the row is 1 * 2, dp[2] = 1 and similarly dp[3] = 1, where dp[i] refers to the ways in which the row of size i can be mined.
And from here upon, build the dp array as: dp[i] = (dp[i - 2] + dp[i - 3]) % 1000000007;
Finally dp[n] would be our answer.
But this will fail here because of the large constraint.
Now, suppose we have an equation like this: [dp[0], dp[1], dp[2]] * M = [dp[1], dp[2], dp[3]], where M is a matrix of size 3 * 3, then we can say [dp[0], dp[1], dp[2]] * M^2 = [dp[2], dp[3], dp[4]].
On generalizing, [dp[0], dp[1], dp[2]] * M^(N - 2) = [dp[n - 2], dp[n - 1], dp[n]] for N > 2
To find the matrix, consider the matrix cells unknown and multiply it with the dp array on the left and equate it with the RHS. Leaving the task upon you, the matrix will be:
0 0 1
1 0 1
0 1 0
Now M^(n - 2) can be found in 27 * log n and after all the multiplications of the above equation, our answer will simply be FinalArray[2] (the last element of our resulting array on the RHS).
Note: You need to take care of taking modulo on every operation to avoid the overflow. See the solution for more references.
AUTHOR’S SOLUTION:
Author’s solution can be found here.