Binomial coefficients
Binomial coefficients are the number of ways to choose a set of elements from distinct elements without regard to order (that is, the number of unordered sets).
Binomial coefficients are also the coefficients in the expansion of (the binomial theorem):
Analytical formula:
Recursive formula (related to Pascal's triangle):
Note that for , the value of is considered to be zero.
Binomial coefficients have many useful properties. Here are the main ones.
In the code:
vector<vector<int>> C(N, vector<int> (N, 0));
for (int i = 0; i < N; i++) {
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; j++) {
C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
}
}
void init_combinatorics() {
fac[0] = 1;
for (int i = 1; i < N; i++) {
fac[i] = 1ll * i * fac[i - 1] % mod;
}
inv[N - 1] = pw(fac[N - 1], mod - 2);
for (int i = N - 2; i >= 0; i--) {
inv[i] = inv[i + 1] * 1ll * (i + 1) % mod;
}
}
int C(int n, int k) {
return 1ll * fac[n] * inv[k] % mod * inv[n - k] % mod;
}