Binomial Coefficients - Part 2

In many problems, it is required to find the answer modulo a large prime, such as 1000000007 (hereby referred to as MAX or m). If the problem involves binomial coefficients, then they have to be calculated modulo MAX too.

It is easy to calculate factorials modulo MAX, because

(a*b) mod m = (a mod m) * (b mod m)

but the same does not hold for division, which makes it tricky to calculate binomial coefficients.

However, the following relation holds :

(a/b) mod m = (a mod m) * (c mod m)

where 'c' is the modular multiplicative inverse[1] of 'b'.

Thus, the relation

C(n, k) = fact(n)/(fact(n-k)*fact(k))

is reduced to

C(n,k) = fact(n)*invfact(n-k)*invfact(k)

where C(a,b) and fact(a) are expressed modulo m, and invfact(a) denotes the multiplicative inverse of fact(a) modulo m. Multiplication is also performed modulo m.

Implementation :

	#define MAX 1000000007
	#define FACT_MAX 250
	int add(int a, int b){
	return (a + b) % MAX;
	}
	int mul(int a, in b){
	return ((long long)a * b) % MAX;
	}
	int powMod(int a, int b){
	int res = 1;
	for (; b; b >>= 1){
	if (b & 1) res = mul(res, a);
	a = mul(a, a);
	}
	return res;
	}
	int modInverse(int a){
	return powMod(a, MAX - 2);
	}
	int fact[FACT_MAX], invfact[FACT_MAX];
	// To generate factorials of numbers up to FACT_MAX.
	// This function should be called once in main()
	void genFact(){
	fact[0] = invfact[0] = 1;
	for (int i = 1; i < FACT_MAX; i++){
	fact[i] = mul(fact[i-1], i);
	invfact[i] = modInverse(fact[i]);
	}
	}
	int C(int n, int k){
	return n < k ? 0 : mul(fact[n], mul(invfact[k], invfact[n-k]));
	}

view raw binomial_coefficients.cpp hosted with ❤ by GitHub

The above implementation employs efficient routines for modular arithmetric.

[1] - http://en.wikipedia.org/wiki/Modular_multiplicative_inverse