nCr with Precomputed Factorials
Count combinations modulo a prime.
Counting Combinations
Many problems ask how many ways to choose r items from n, written nCr. Contests want that count under a prime modulus. 🧮
The Factorial Formula
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.
# nCr = n! / (r! * (n-r)!)All lessons in this course
- Work Modulo a Prime
- Fast Modular Exponentiation
- Modular Inverse via Fermat
- nCr with Precomputed Factorials