c++algorithmmodulusmodular-arithmeticbinomial-coefficients

Finding binomial coefficient for large n and k modulo m

I want to compute nCk mod m with following constraints:

n<=10^18

k<=10^5

m=10^9+7

I have read this article:

Calculating Binomial Coefficient (nCk) for large n & k

But here value of m is 1009. Hence using Lucas theorem, we need only to calculate 1009*1009 different values of aCb where a,b<=1009

How to do it with above constraints. I cannot make a array of O(m*k) space complexity with given constraints.

Help!

Solution

  • Just use the fact that 

    (n, k) = n! / k! / (n - k)! = n*(n-1)*...*(n-k+1)/[k*(k-1)*...*1]

    so you actually have just 2*k=2*10^5 factors. For the inverse of a number you can use suggestion of kfx since your m is prime.