Finding binomial coefficient for large n and k modulo m

Question

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!

Carlotacarlotta

Answer 1

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.

Extract

Right, for the OP's small k this will work, but will not generalize for larger values. – Cabob

@Cabob Can you please explain, why this will not work for larger values? – Hushhush

@Hushhush I can: imagine just (1000, 200) for C++. The result is too big (you can't store it in any default c++ data). – Lait

Answer 2

First, you don't need to pre-compute and store all the possible aCb values! they can be computed per case.

Second, for the special case when (k < m) and (n < m^2), the Lucas theorem easily reduces to the following result:

(n choose k) mod m = ((n mod m) choose k) mod m

then since (n mod m) < 10^9+7 you can simply use the code proposed by @kfx.

Brandish

Answer 3

We want to compute nCk (mod p). I'll handle when 0 <= k <= p-2, because Lucas's theorem handles the rest.

Wilson's theorem states that for prime p, (p-1)! = -1 (mod p), or equivalently (p-2)! = 1 (mod p) (by division).

By division: (k!)^(-1) = (p-2)!/(k!) = (p-2)(p-3)...(k+1) (mod p)

Thus, the binomial coefficient is n!/(k!(n-k)!) = n(n-1)...(n-k+1)/(k!) = n(n-1)...(n-k+1)(p-2)(p-3)...(k+1) (mod p)

Voila. You don't have to do any inverse computations or anything like that. It's also fairly easy to code. A couple optimizations to consider: (1) you can replace (p-2)(p-3)... with (-2)(-3)...; (2) nCk is symmetric in the sense that nCk = nC(n-k) so choose the half that requires you to do less computations.

Planography

0 Excellent! It's way too late to help OP, but it gave me ideas about solving a different problem. – Midway

Answer 4

Realy easy way to solve this problem is using just two things:

1. Next binomial coefficient in row n is nC(k + 1) = nCk * (n - k + 1) / k;
2. From Fermat's little theorem and modular multiplicative inverses: k^(-1) = k^(m - 2) mod m or other words ModPow(k, m - 2, m). Where ModPow is function performs modulus division on a number raised to the power of another number. Can easily implemented by exponentiation by squaring.

Now we can compute nC(k + 1) mod m = [(nCk mod m * (n - k + 1) mod m) * ModPow(k, m - 2, m)] mod m. In cycle start from k = 1 to k and nCk mod m = 1 we can fast find nCk mod m.

Careless