The idea
The number of ways to choose k items out of n is C(n, k) = n! / (k! · (n−k)!). Answers are usually asked modulo a prime p, where division becomes multiplication by a modular inverse: a⁻¹ = a^(p−2) mod p.
Precompute factorials and inverse factorials once; every C(n, k) is then O(1).
Stars and bars: sharing n identical items among k children, where a child may get none, is the same as placing k−1 dividers among the items: C(n + k − 1, k − 1) ways. If every child must get at least one, it is C(n − 1, k − 1).
Sample problem
62. Unique Paths ↗ Medium
A robot stands in the top-left cell of an m × n grid and can only move right or down. Count the different paths to the bottom-right cell.
m = 3, n = 7 output = 28
Why the solution works
A table that adds “paths from above” and “paths from the left” works, but the count can be seen directly.
Every path consists of exactly m−1 downs and n−1 rights; only their order differs. Choosing which of the m+n−2 moves are the downs fixes the path, so the answer is the binomial coefficient C(m+n−2, m−1).
The loop builds that coefficient one factor at a time. After step i the value is C(total−k+i, i), itself a whole number, so the division is always exact. Using the smaller of m−1 and n−1 as k keeps the loop short.
Complexity: O(min(m, n)) time, O(1) memory.
Watch out
- The
a^(p−2)inverse only works when the modulus is prime. - Precompute far enough: stars and bars needs factorials up to n + k.
- After a subtraction add MOD before taking the remainder, so the result is not negative.