Binomial Coefficients (nCr)
O(1) per query after O(n) setupPrecompute factorials and inverse factorials once, then answer any nCr mod a prime in constant time. The inverse factorials come from a single modular inverse plus a backward sweep, so setup is one O(log MOD) power total.
// use it on
CSES: Binomial Coefficients ↗
Up to 10^5 nCr queries with n up to 10^6. Precompute once, answer each in O(1).
// the code
const long long MOD = 998244353;
vector<long long> fact, inv_fact;
long long power(long long b, long long e) {
long long r = 1;
for (b %= MOD; e > 0; e >>= 1, b = b * b % MOD)
if (e & 1) r = r * b % MOD;
return r;
}
void init_comb(int N) {
fact.assign(N + 1, 1);
for (int i = 1; i <= N; i++) fact[i] = fact[i - 1] * i % MOD;
inv_fact.assign(N + 1, 1);
inv_fact[N] = power(fact[N], MOD - 2);
for (int i = N; i >= 1; i--)
inv_fact[i - 1] = inv_fact[i] * i % MOD;
}
long long C(int n, int r) {
if (r < 0 || r > n) return 0;
return fact[n] * inv_fact[r] % MOD * inv_fact[n - r] % MOD;
}