nCr with Precomputed Factorials

Many problems ask how many ways to choose r items from n, written nCr. Contests want that count under a prime modulus. 🧮

The classic formula is nCr equals n factorial divided by r factorial times n minus r factorial. The catch is that division under a mod.

A single factorial grows astronomically, so you take each one mod p. That keeps every value small while the formula stays exact under the modulus.

Build a fact array once up to the largest n you need. Each entry is the previous times the index, taken mod p as you go.

The formula divides by two factorials, so you need their modular inverses. Recall the inverse turns division into a clean multiplication.

Compute the inverse of the largest factorial just once with Fermat, using pow with exponent p minus 2. That single call seeds the rest.

Get the other inverse factorials in one backward pass, each from the next times the index. No extra pow calls needed.

Now nCr is just fact[n] times inv_fact[r] times inv_fact[n minus r], all mod p. Three lookups and two multiplies per query.

After the precompute, every combination answer is O(1). That is why this pattern shines when a problem asks thousands of nCr values.

If r is negative or larger than n, the answer is 0. Check that bound first so you never index outside your factorial arrays.

Set your array size to the maximum n across all queries plus a little margin. A too-small limit is a common cause of index errors here.

After precomputing, how fast is one nCr query?

You precompute factorials and their inverses once, then answer each nCr in O(1) with three lookups. Guard the r bounds and size arrays big enough. 🏆