Binomial Coefficients

Precomputed factorial and inverse factorial for O(1) nCr and nPr queries modulo a prime.

[Combinatorics]|

Jul 9, 2026

|explanatory_notes.md|

#binomial#nCr#nPr#factorial#combinatorics

$cat source_code/

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll MOD = 1e9 + 7;
const int MAXN = 2e6 + 5;
ll fact[MAXN], inv_fact[MAXN];

ll power(ll base, ll exp, ll mod) {
    ll res = 1; base %= mod;
    while (exp > 0) {
        if (exp & 1) res = res * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}

void initFact() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++)
        fact[i] = fact[i - 1] * i % MOD;
    inv_fact[MAXN - 1] = power(fact[MAXN - 1], MOD - 2, MOD);
    for (int i = MAXN - 2; i >= 0; i--)
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD;
}

ll nCr(ll n, ll r) {
    if (r < 0 || r > n) return 0;
    return fact[n] % MOD * inv_fact[r] % MOD * inv_fact[n - r] % MOD;
}

ll nPr(ll n, ll r) {
    if (r < 0 || r > n) return 0;
    return fact[n] % MOD * inv_fact[n - r] % MOD;
}

36 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

Binomial Coefficients

Precompute factorials and inverse factorials for $O(1)$ modular $\binom{n}{r}$ queries.

Formula

\binom{n}{r} = \frac{n!}{r! \cdot (n-r)!} \mod p

Using Fermat's little theorem: $a^{-1} \equiv a^{p-2} \pmod{p}$ for prime $p$ .

Properties

Pascal's identity:

\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}

Sum:

\sum_{k=0}^{n} \binom{n}{k} = 2^n

Boundary:

\binom{n}{0} = \binom{n}{n} = 1

When to Use

Counting subsets, combinations

Grid path counting: paths from

(0,0)

(n,m) = \binom{n+m}{n}

Intermediate step in inclusion-exclusion

Notes

Inverse factorials computed in

O(n)

using the identity

\text{inv}[i] = (i+1) \cdot \text{inv}[i+1]

Only works when MOD is prime

Complexity

Precomputation —

O(n)

Query —

O(1)