Calculated nCr mod m (n choose r) for large values of n (10^9)

Question

Now that CodeSprint 3 is over, I've been wondering how to solve this problem. We need to simply calculate nCr mod 142857 for large values of r and n (0<=n<=10^9 ; 0<=r<=n). I used a recursive method which goes through min(r, n-r) iterations to calculate the combination. Turns out this wasn't efficient enough. I've tried a few different methods, but they all seem to not be efficient enough. Any suggestions?

Answer 1

For non-prime mod, factor it (142857 = 3^3 * 11 * 13 * 37) and compute C(n,k) mod p^q for each prime factor of the mod using the general Lucas theorem, and combine them using Chinese remainder theorem.

For example, C(234, 44) mod 142857 = 6084, then

• C(234, 44) mod 3^3 = 9
• C(234, 44) mod 11 = 1
• C(234, 44) mod 13 = 0
• C(234, 44) mod 37 = 16

The Chinese Remainder theorem involves finding x such that

• x = 9 mod 3^3
• x = 1 mod 11
• x = 0 mod 13
• x = 16 mod 37

The result is x = 6084.

Example

C(234, 44) mod 3^3

First convert n, k, and n-k to base p

n = 234_10 = 22200_3

k = 44_10 = 1122_3

r = n-k = 190_10 = 21001_3

Next find the number of carries

e[i] = number of carries from i to end
e   4 3 2 1 0
        1 1
r   2 1 0 0 1
k     1 1 2 2
n   2 2 2 0 0

Now create the factorial function needed for general Lucas

def f(n, p):
    r = 1
    for i in range(1, n+1):
        if i % p != 0:
            r *= i
    return r

Since q = 3, you will consider only three digits of the base p representation at a time

So

f(222_3, 3)/[f(210_3, 3) * f(011_3, 3)] *
f(220_3, 3)/[f(100_3, 3) * f(112_3, 3)] *
f(200_3, 3)/[f(001_3, 3) * f(122_3, 3)] = 6719344775 / 7

Now

s = 1 if p = 2 and q >= 3 else -1

Then

p^e[0] * s * 6719344775 / 7 mod 3^3
e[0] = 2
p^e[0] = 3^2 = 9
s = -1
p^e[0] * s * 6719344775 = -60474102975

Now you have

-60474102975 / 7 mod 3^3

This is a linear congruence and can be solved with

ModularInverse(7, 3^3) = 4
4 * -60474102975 mod 27 = 9

Hence C(234, 44) mod 3^3 = 9