← all categories

Ncr Factorials 5e3e87bd

nCr mod a prime via precomputed factorials + inverse factorials. Call build(maxn, MOD) once, then choose(n, k) is O(1). MOD must be prime and > maxn.

Time: O(maxn) build, O(1) per query. tested

content/math/ncr-factorials.h

struct Binomial {
    ll MOD;
    vector<ll> fact, inv;

    void build(int maxn, ll mod) {
        MOD = mod;
        fact.assign(maxn, 1);
        for (int i = 1; i < maxn; i++) fact[i] = fact[i - 1] * i % MOD;
        inv.assign(maxn, 1);
        inv[maxn - 1] = invMod(fact[maxn - 1], MOD);
        for (int i = maxn - 2; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % MOD;
    }

    ll choose(ll n, ll k) {
        if (k < 0 || k > n) return 0;
        return fact[n] * inv[k] % MOD * inv[n - k] % MOD;
    }
};