Chapter 25
HomeCombinatorics problems ask "how many ways" — how many ways to choose K items from N. The answer is nCr = n! / (r! × (n−r)!).
Since we work modulo M, division becomes multiplication by the modular inverse. By Fermat's Little Theorem:
a⁻¹ ≡ a^(M−2) (mod M) when M is prime
So we can compute inverses using our mod_pow function.
const long long MOD = 1e9 + 7;
long long mod_pow(long long a, long long b, long long m);
// ... (from chapter 23/24)
long long mod_inv(long long a) {
return mod_pow(a, MOD - 2, MOD);
}
long long nCr(int n, int r) {
if (r < 0 || r > n) return 0;
long long num = 1, den = 1;
for (int i = 1; i <= n; i++) num = num * i % MOD;
for (int i = 1; i <= r; i++) den = den * i % MOD;
for (int i = 1; i <= n - r; i++) den = den * i % MOD;
return num * mod_inv(den) % MOD;
}
This computes factorials from scratch each call — fine for one-off, slow for many queries.
const MOD: u64 = 1_000_000_007;
fn mod_pow(a: u64, b: u64, m: u64) -> u64;
// ... (from chapter 23/24)
fn mod_inv(a: u64) -> u64 {
mod_pow(a, MOD - 2, MOD)
}
fn ncr(n: u64, r: u64) -> u64 {
if r > n { return 0; }
let mut num = 1;
let mut den = 1;
for i in 1..=n { num = num * i % MOD; }
for i in 1..=r { den = den * i % MOD; }
for i in 1..=(n - r) { den = den * i % MOD; }
num * mod_inv(den) % MOD
}