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 ?
1 Answer
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) so
V(0) = [ 3 1 0 ] and
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.
- 1
helps to have abasicfamiliarity with linear algebra. Not that basic...UmNyobe– UmNyobe2014-09-04 09:59:11 +00:00Commented Sep 4, 2014 at 9:59 - aggree @UmNyobe ,
@kevincan you please explain more in detail .. How you declare M .. on which basis you have take MHybrisHelp– HybrisHelp2014-09-04 10:10:07 +00:00Commented Sep 4, 2014 at 10:10 - 1I'm not sure if it would be possible to mod all calculations and arrive at correct solution using this approach.Euphoric– Euphoric2014-09-04 10:12:39 +00:00Commented Sep 4, 2014 at 10:12
-
@kevinand can you help me give exact program (if possible) cause i am newbie in algorithm. So i want to see this how can you implement such matrix and all .. If possible plz give program.HybrisHelp– HybrisHelp2014-09-04 10:15:37 +00:00Commented Sep 4, 2014 at 10:15 - 1@ankit337: you can get further help only after presenting evidence of some effort on your part. Most of us get paid to program. Why should we work for free?kevin cline– kevin cline2014-09-05 01:43:24 +00:00Commented Sep 5, 2014 at 1:43
First I have thought recursive solution with dynamic programming but it take more timeHang on... It shouldn't. Post the dynamic programming version.