Choosing under a modulus
Counting problems often report answers as a number of combinations reduced by a large prime. A binomial coefficient is a factorial divided by two factorials, but division is not direct under a modulus, so you use modular inverses of factorials.
Precompute once
- Build a table of factorials under the modulus up to the largest needed value.
- Build a matching table of their modular inverses, typically by inverting the top factorial once and walking down.
- Each binomial is then the top factorial times the two inverse factorials, all under the modulus.
With both tables ready, every coefficient is a constant number of multiplications, so many queries are answered fast.
Useful identities
Pascal style recurrences also work under a modulus when the prime exceeds the indices. For indices that reach or exceed the prime, the factorial method breaks down and a digit based theorem is required instead.
Key idea
Modular combinatorics precomputes factorials and their inverses under a prime so each binomial coefficient is a few multiplications, answering many counting queries quickly when indices stay below the prime.