# 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

## 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.

• `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