-1

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
4

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 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
  • 1
    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
  • 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 Sep 5 '14 at 1:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.