I just solve this but want know more efficient way to do matrix multiplication
M : ------ 1 1 0 0 0 5 3 2 0
f[n] = M^n
I have implemented using Exponentiation_by_squaring
Is there more efficient then this ?
Since N can be as large as 10^12 it should have been clear that iterating from 1 to N is not the desired solution. The key insight is that the recursion can be rewritten as V(i) = M * V(i-1), where
V(i) = [RR(i), MM(i), PP(i)] (a column vector)
V(0) = [ 3 1 0 ]
M = | 1 0 3 | | 1 0 2 | | 0 5 0 |
Now V(N) = M^N * V(0)
We can calculate M^N in log(N) time by repeatedly squaring:
M^2 = M * M M^4 = M^2 * M^2 ...
Perform all calculations mod 100000006 to avoid accumulating large numbers.
To arrive at this solution, it helps to have a basic familiarity with linear algebra.