Подсчёт и перечисление комбинаторных объектов: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
== Факториал == | |||
{| width="100%" | |||
| width=50% | | |||
const long long MOD = 1e9 + 7; | |||
long long factorial(int n) { | |||
static vector<long long> memo(1e5); | |||
long long &res = memo[n]; | |||
if (res) | |||
return res; | |||
if (n <= 1) | |||
return res = 1; | |||
return res = factorial(n - 1) * n % MOD; | |||
} | |||
| width="10px" | | |||
| width=50% | | |||
const long long MOD = 1e9 + 7; | |||
vector<long long> precalcFactorials() { | |||
vector<long long> memo(1e5); | |||
memo[0] = 1; | |||
for (int i = 1; i < memo.size(); i++) | |||
memo[i] = memo[i - 1] * i % MOD; | |||
return memo; | |||
} | |||
long long factorial(int n) { | |||
static vector<long long> memo = precalcFactorials(); | |||
return memo[n]; | |||
} | |||
|} | |||
== Число сочетаний из n по k == | |||
{| width="100%" | |||
| width=50% | | |||
const long long MOD = 1e9 + 7; | |||
long long c(int n, int k) { | |||
static vector<vector<long long>> memo(1000, vector<long long>(1000, -1)); | |||
long long &res = memo[n][k]; | |||
if (res != -1) | |||
return res; | |||
if (k == 0 || k == n) | |||
return res = 1; | |||
return res = (c(n - 1, k) + c(n - 1, k - 1)) % MOD; | |||
} | |||
| width="10px" | | |||
| width=50% | | |||
const long long MOD = 1e9 + 7; | |||
long long binPow(long long x, long long p, long long mod) { | |||
if (!p) | |||
return 1; | |||
if (p % 2) | |||
return binPow(x, p - 1, mod) * x % mod; | |||
long long r = binPow(x, p / 2, mod); | |||
return r * r % mod; | |||
} | |||
long long inv(long long x) { | |||
return binPow(x, MOD - 2, MOD); | |||
} | |||
long long c(int n, int k) { | |||
return factorial(n) * inv(factorial(k)) % MOD * inv(factorial(n - k)) % MOD; | |||
} | |||
|} | |||
== Ссылки на задачи == | == Ссылки на задачи == | ||
| Строка 10: | Строка 90: | ||
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%93%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D1%86%D0%B8%D1%8F_%D0%BA%D0%BE%D0%BC%D0%B1%D0%B8%D0%BD%D0%B0%D1%82%D0%BE%D1%80%D0%BD%D1%8B%D1%85_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D0%BE%D0%B2_%D0%B2_%D0%BB%D0%B5%D0%BA%D1%81%D0%B8%D0%BA%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%BC_%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BA%D0%B5 neerc.ifmo.ru/wiki — Генерация комбинаторных объектов в лексикографическом порядке] | * [http://neerc.ifmo.ru/wiki/index.php?title=%D0%93%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D1%86%D0%B8%D1%8F_%D0%BA%D0%BE%D0%BC%D0%B1%D0%B8%D0%BD%D0%B0%D1%82%D0%BE%D1%80%D0%BD%D1%8B%D1%85_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D0%BE%D0%B2_%D0%B2_%D0%BB%D0%B5%D0%BA%D1%81%D0%B8%D0%BA%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%BC_%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BA%D0%B5 neerc.ifmo.ru/wiki — Генерация комбинаторных объектов в лексикографическом порядке] | ||
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D1%81%D0%BB%D0%B5%D0%B4%D1%83%D1%8E%D1%89%D0%B5%D0%B3%D0%BE_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D0%B0 neerc.ifmo.ru/wiki — Получение следующего объекта] | * [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D1%81%D0%BB%D0%B5%D0%B4%D1%83%D1%8E%D1%89%D0%B5%D0%B3%D0%BE_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D0%B0 neerc.ifmo.ru/wiki — Получение следующего объекта] | ||
* [http://brestprog.neocities.org/lections/combinatorics.html brestprog.neocities.org — Основные элементы комбинаторики] | |||
* [http://informatics.mccme.ru/course/view.php?id=21 informatics.mccme.ru — Курс «Комбинаторные алгоритмы» — часть 1] | * [http://informatics.mccme.ru/course/view.php?id=21 informatics.mccme.ru — Курс «Комбинаторные алгоритмы» — часть 1] | ||
[[Категория:Комбинаторика]] | [[Категория:Комбинаторика]] | ||
Текущая версия от 11:54, 20 ноября 2022
Факториал
const long long MOD = 1e9 + 7;
long long factorial(int n) {
static vector<long long> memo(1e5);
long long &res = memo[n];
if (res)
return res;
if (n <= 1)
return res = 1;
return res = factorial(n - 1) * n % MOD;
}
|
const long long MOD = 1e9 + 7;
vector<long long> precalcFactorials() {
vector<long long> memo(1e5);
memo[0] = 1;
for (int i = 1; i < memo.size(); i++)
memo[i] = memo[i - 1] * i % MOD;
return memo;
}
long long factorial(int n) {
static vector<long long> memo = precalcFactorials();
return memo[n];
}
|
Число сочетаний из n по k
const long long MOD = 1e9 + 7;
long long c(int n, int k) {
static vector<vector<long long>> memo(1000, vector<long long>(1000, -1));
long long &res = memo[n][k];
if (res != -1)
return res;
if (k == 0 || k == n)
return res = 1;
return res = (c(n - 1, k) + c(n - 1, k - 1)) % MOD;
}
|
const long long MOD = 1e9 + 7;
long long binPow(long long x, long long p, long long mod) {
if (!p)
return 1;
if (p % 2)
return binPow(x, p - 1, mod) * x % mod;
long long r = binPow(x, p / 2, mod);
return r * r % mod;
}
long long inv(long long x) {
return binPow(x, MOD - 2, MOD);
}
long long c(int n, int k) {
return factorial(n) * inv(factorial(k)) % MOD * inv(factorial(n - k)) % MOD;
}
|