Биномиальные коэффициенты
Биномиальные коэффициенты — это количество способов выбора набора из элементов из различных элементов без учёта порядка (то есть число неупорядоченных множеств).
Биномиальные коэффициенты также являются коэффициентами при разложении (биномиальная теорема):
Аналитическая формула:
Рекуррентная формула (связанная с треугольником Паскаля):
Заметим, что для значение считается равным нулю.
Биномиальные коэффициенты обладают множеством полезных свойств. Приведём основные из них.
В коде:
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;
}