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

However, the following relation holds :

Thus, the relation

Implementation :

The above implementation employs efficient routines for modular arithmetric.

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

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 :

The above implementation employs efficient routines for modular arithmetric.

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

It's important to note that this relation:

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

isn't always true.

For example:

(7*8) mod 13 = (7 mod 13) * (8 mod 13)

4 = 56 !!!

True. The correct relation is,

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

@DiĆ³genes : Thanks for the observation!