cauchyk's blog

Matrix Exponentiation
By cauchyk, 14 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

14 years ago, # |
  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
  • 12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "You can calculate Cnk in such a way for not prime modules too." how can i calc it for not primes modules, since i am using euclids algorithm i cant get it right for not prime modules.

    → Reply
    • 12 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      it's difficult to explain in a few words. look at the code

      → Reply
      • 12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Your ASS() function introduces undefined behavior, which can be anything, including the program continuing without any failure or subtly subverting the output data. Why not just use assert() from the standard library?

        → Reply
        • 12 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Because it looks a way cooler that way.

          → Reply
        • 12 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          this function introduces RE. assert() function will not work in release. can you offer me the right way?

          → Reply
          • 12 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yes: the easiest way is to replace ++*(int*)0 with abort().

            → Reply
14 years ago, # |
  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
»
12 years ago, # |
  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