Find nCr mod M where M is not prime

1.1k views Asked by At

I have to find nCrmod M where M is not a prime number. How can find that. I know that i need to find the inverse modulo but how it is going to be implemented if the number M is non-prime.

1

There are 1 answers

0
AudioBubble On BEST ANSWER

You can calculate it by the memoization nCr = (n-1)Cr + (n-1)C(r-1) for M<=5000. You can visit the link for more info http://discuss.codechef.com/questions/3869/best-known-algos-for-calculating-ncr-m