Binomial Coefficient

$\left(\genfrac{}{}{0ex}{}{n}{m}\right)=\frac{n!}{(n-m)!m!}=\frac{n(n-1)\cdots (n-k-1)}{1\cdot 2\cdot 3\cdots k}$

Implementation stolen from: https://cp-algorithms.com/combinatorics/binomial-coefficients.html#improved-implementation

int C(int n, int k) {
    double res = 1;
    for (int i = 1; i <= k; ++i)
        res = res * (n - k + i) / i;
    return (int)(res + 0.01)

A simple recursive implementation

int choose(int n, int k) {
    if (k == 0 || k == n) return 1;
    if (k > n) return 0;
    return (n * choose(n - 1, k - 1)) / k;
}

Warning

Recently, I tried to use this formula for this Codeforces problem https://codeforces.com/contest/1999/submission/277997377, but I ran into integer overflow problems, even after using long long.

They do something like this in the solution https://codeforces.com/blog/entry/132373 (Problem F). This is the tourist solution https://codeforces.com/contest/1999/submission/274741514

These implementations use a different formula for modulus.

Binomial coefficient with $\%$ MOD

Learned this from CP algorithms:

• https://cp-algorithms.com/combinatorics/binomial-coefficients.html#binomial-coefficient-modulo-large-prime

You precompute a factorial table.

int factorial[MAXN];
factorial[0] = 1;
for (int i = 1; i <= MAXN; i++) {
    factorial[i] = factorial[i - 1] * i % MOD;
}

Define your modular inverse:

int inv(int a) {
  return a <= 1 ? a : MOD - (long long)(MOD/a) * inv(MOD % a) % MOD;
}

• https://cp-algorithms.com/algebra/module-inverse.html#mod-inv-all-num

int C(int n, int k) {
    return factorial[n] * inv(factorial[k] * factorial[n - k] % MOD) % MOD;
}

Some Properties

Another Note: $\left(\genfrac{}{}{0ex}{}{n}{m}\right)=\left(\genfrac{}{}{0ex}{}{n}{n-m}\right)$

Related

• Binomial Theorem