# optimise my solution

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 ?

• The whole modulo thing makes me think there could be some kind of mathematical hackery to turn it into simple equation. – Euphoric Sep 4 '14 at 6:54
• yes I also think big number multiplication take more time – HybrisHelp Sep 4 '14 at 6:55
• Shouldn't the modulo also be in calculateProduction for each variable? The way you have it now seems to be incorrect. – Euphoric Sep 4 '14 at 7:00
• First I have thought recursive solution with dynamic programming but it take more time Hang on... It shouldn't. Post the dynamic programming version. – UmNyobe Sep 4 '14 at 7:37
• sure I will update my post .. – HybrisHelp Sep 4 '14 at 7:45

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.

• helps to have a basic familiarity with linear algebra. Not that basic... – UmNyobe Sep 4 '14 at 9:59
• aggree @UmNyobe , @kevin can you please explain more in detail .. How you declare M .. on which basis you have take M – HybrisHelp Sep 4 '14 at 10:10
• I'm not sure if it would be possible to mod all calculations and arrive at correct solution using this approach. – Euphoric Sep 4 '14 at 10:12
• @kevin and 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 Sep 4 '14 at 10:15
• @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 Sep 5 '14 at 1:43