How to calculate nCr mod m when m is a prime number
ncr=n!/r!(n-r)!
(n!%m*inverse(r!)%m*inverse((n-r)!)%m)%m
fact[i]=i*fact[i-1]%m
inverse[i]=fact[i]^(m-2)%m
by fermets' little theorm
inverse(b)%m=b^(m-2)%m
and we can calculate power of any number using fast exponentiation
to avoid the time limitation.
as we are using arrays to save our results it is good enough (n<=10000000)
If we have to find nCr mod m(where m is not prime), we can factorize m into primes and then use Chinese Remainder Theorem(CRT) to find nCr mod m.
also, we can calculate nCr for any m which is small enough (say m ≤ 5000) or small n and r (say r ≤ n ≤ 5000) by using the following recursion with memoization having time complexity O(n*r)
nCr = n-1Cr + n-1Cr-1
ncr=n!/r!(n-r)!
(n!%m*inverse(r!)%m*inverse((n-r)!)%m)%m
fact[i]=i*fact[i-1]%m
inverse[i]=fact[i]^(m-2)%m
by fermets' little theorm
inverse(b)%m=b^(m-2)%m
and we can calculate power of any number using fast exponentiation
to avoid the time limitation.
as we are using arrays to save our results it is good enough (n<=10000000)
If we have to find nCr mod m(where m is not prime), we can factorize m into primes and then use Chinese Remainder Theorem(CRT) to find nCr mod m.
also, we can calculate nCr for any m which is small enough (say m ≤ 5000) or small n and r (say r ≤ n ≤ 5000) by using the following recursion with memoization having time complexity O(n*r)
nCr = n-1Cr + n-1Cr-1
No comments:
Post a Comment