PROBLEM LINK:
Author: Asif Haque
Tester: Jingbo Shang
Editorialist: Jingbo Shang
DIFFICULTY:
Medium
PREREQUISITES:
Fast Matrix Power with Mod
PROBLEM:
Given a m-order linear recurrence, calculate the n-th number (mod 10^9+7).
EXPLANATION:
There are two key points in this problem:
Write the linear recurrence in matrix representation. That is using a m×m matrix to state one step of recurrence.
Fast calculate the matrix power operation. That is using O(m^3 logn) time to get A^n mod 10^9+7
Let’s take a example of Fibonacci Numbers.
fib[n] = fib[n - 1] + fib[n - 2]
This is a 2-order linear recurrence. And we can write this as the following matrix representation:
(fib[n-1],fib[n]) * (0, 1; 1, 1) = (fib[n], fib[n+1])
Here (0, 1; 1, 1) is a 2*2 matrix, denote as A.
After that, we need to calculate A^n mod 10^9+7.
We can prepare A^1,A^2,A^4…A^logn in O(m^3 logn) time. And then, multiple corresponding matrices together to get A^n. Based on the binary expression of n,it is obvious that these logn matrices will be multiplied at most once. Therefore, we can get the answer in O(m^3 logn).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.