C(n, k) counts k-subsets of n items. It is also the grid-path count from the DP I lesson: C(n+m, n) ways right-and-down. Constraints decide the algorithm:
- n ≤ 30 — compute with a loop of 64-bit ints, or even Pascal's triangle.
- n ≤ 1e6, p prime, many queries — prefix factorials.
- n ≤ 1e18, k ≤ 1e6 — multiplicative loop ans = ans * (n-i) / (i+1).
- n huge, p small — Lucas' theorem (not this lesson).
CSES Binomial Coefficients is the factorial table. Overflow and 'divide as you go in integers' are the WA modes.
function nCrMod(n, k, mod) {
if (k < 0 || k > n) return 0;
const fact = Array(n + 1).fill(1);
for (let i = 1; i <= n; i++) fact[i] = Number((BigInt(fact[i - 1]) * BigInt(i)) % BigInt(mod));
const inv = (x) => modPow(x, mod - 2, mod);
const invN = inv(fact[n]);
// invFact[n] = 1/n!, then walk down if you need many queries
const denom = Number((BigInt(fact[k]) * BigInt(fact[n - k])) % BigInt(mod));
return Number((BigInt(fact[n]) * BigInt(modPow(denom, mod - 2, mod))) % BigInt(mod));
}Checks 0/2