# nCr

## Problem

The problem can be found here. The statement of this problem is extremely simple, in short, you need to calculate the ${n \choose r} \bmod M$ where M is 142857.

## Lucas Theorem

If 142857 is a prime number, then we can just use the Lucas theorem to solve it. However, $142857 = 3^3 \times 11 \times 13 \times 37$, that is why the problem is marked as an expert level problem in hackerrank.

The core idea of using Lucas theorem to calculate ${n \choose r} \bmod P$ where P is a prime number is to represent $n!$ as $a \times P^e$ where a is relative prime to P. To calculate the representation of $n!$, we can group $1 \times 2 \times \cdots \times n$ of P elements each, so it can be expressed as $(1 \times 2 \cdots \times (P -1)) \times P \times ((P+1)$ $\times$ $(P+2) \cdots \times (2P - 1)) \times$ $2P \cdots$, so that $1 \times 2 \times \cdots \times (P - 1)$ is relative prime to P, and each group mod P is of the same result.

And then use Wilson theorem which said that $(P - 1)! \equiv -1 (\bmod P)$. We can finally get the solution to calculate $n! = a \times P^e$. The python code as follow:

Notice the tricky in the last two line of the above code. Since $(P - 1)! = 1 (\bmod P)$, so if the number of group is even, then the result is just facts[n % p] % p, otherwise is -facts[n % p] % p, which is equivelent to (p - facts[n % p]) % p.

And then we can express ${n \choose r} = {n! \over {r! \times (n - r)!}}$, calculate $n! = a_1 \times P^{e_1}$, $k! = a_2 \times P^{e_2}$ and $(n - k)! = a_3 \times P^{e_3}$. Then if $e_1 > e_2 + e_3$, ${n \choose k}$ must be zero mod P, otherwise, the result should be a1 * modinv (a2 * a3, P) where modinv is the modulo inverse function.

## Generalize to this Problem

We can use very similar idea to calculate $n! \bmod P^a$ for $a\ge1$. Let $b = max \{i | n! \bmod P^i == 0, i \in \mathcal{N} \}$, then we need to calculate largest divisors of $n!$ relative prime to $P^a$.

This time we group $1 \times 2 \cdots \times n$ into group each has $P^a$ items. We first pre calculate the array facts[0..P^a], facts[i] is the largest divisors of $i!$ relative prime to $P^a$ mod $P^a$. Then we can use the same strategy when calculate $n! \bmod P^a$.

The above code is just to calculate ${n \choose r} \bmod P^a$. The function n_fact_fact is just to calculate the largest divisor of $n!$ mod $P^a$ which is relative to $P^a$. And get_power is to get the largest number of b such that ${n \choose r} \equiv 0 (\bmod P^b)$.

Finally, we can use Chinese Remainder Theorem to solve the problem. Since $142857 = 3^3 \times 11 \times 13 \times 37$, we can calculate ${n \choose r} \bmod 3^3$, ${n \choose r} \bmod 11$, ${n \choose r} \bmod 13$ and ${n \choose r} \bmod 37$, and the modulo numbers are relative prime to each other, so we can use it to finally get the answer.

You can find the whole solution in C++ and Python here.

11 April 2015