cauchyk's blog

Matrix Exponentiation
By cauchyk, 15 years ago, In English
Can nCr % x (n choose r modulo any value)
computed by matrix exponentiation? if yes, how?
  • Vote: I like it
  • 0
  • Vote: I do not like it

15 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
i think you need fast method to calculate binomial coefficients for large n and k.

if n and k is less than 10^6, or mudule less than 10^6, you can precalc all factoials up to 10^6.

You can calculate Cnk in such a way for not prime modules too.
→ Reply
15 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

If N is very large (10^100 for example), and R is reasonably small (100 for instance), you can create (R+1)x(R+1) matrix A, which has ones on the main diagonal and on the diagonal above main, than compute v(A^N), where v is [1,0,0,0,...,0]. Last element of resulting vector will be the answer.

I believe this is what you were looking for

 

→ Reply
»
14 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can you/someone here please provide a problem link that needs this technique so that I can try my solution on that?

Thanks in advance :-)

→ Reply