CONCEPT · Master
Binomial coefficients
also nCr · n choose k · factorials
C(n,k)=n!/(k!(n-k)!). Mod a prime, multiply by inverses. Precompute fact and invFact when n ≤ 1e6 and you have many queries.
Intuition
Choosing k is choosing the complement. The formula is a ratio of falling factorials, not a float.
When to reach for it
- Grid paths, subset counts, stars and bars
- CSES Binomial Coefficients
- Any 'how many ways' that factors into choose
Usual pits
- k > n → 0, not a crash
- Inverse of k! when k ≥ p
- a*b*c / gcd is not lcm and not C(n,k)
- Overflow if you multiply the whole falling factorial before dividing