Подсчёт и перечисление комбинаторных объектов - История изменений

Ctrlalt в 11:54, 20 ноября 2022

2022-11-20T11:54:26Z

← Предыдущая версия		Версия от 11:54, 20 ноября 2022
Строка 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;
			}
			\|}

	== Ссылки на задачи ==		== Ссылки на задачи ==

Ctrlalt: /* Ссылки */

2016-01-27T20:07:04Z

Ссылки

← Предыдущая версия		Версия от 20:07, 27 января 2016
Строка 10:		Строка 10:
	* [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]

	[[Категория:Комбинаторика]]		[[Категория:Комбинаторика]]

Ctrlalt: /* Ссылки на задачи */

2014-08-26T19:43:01Z

Ссылки на задачи

← Предыдущая версия		Версия от 19:43, 26 августа 2014
Строка 1:		Строка 1:
	== Ссылки на задачи ==		== Ссылки на задачи ==

			* [http://acmp.ru/?main=task&id_task=77 ACMP #77 — Нолики]
	* [http://acmp.ru/?main=task&id_task=156 ACMP #156 — Шахматы - 2]		* [http://acmp.ru/?main=task&id_task=156 ACMP #156 — Шахматы - 2]
	* [http://acmp.ru/?main=task&id_task=157 ACMP #157 — Карточки]		* [http://acmp.ru/?main=task&id_task=157 ACMP #157 — Карточки]

Ctrlalt: Новая страница: «== Ссылки на задачи == * [http://acmp.ru/?main=task&id_task=156 ACMP #156 — Шахматы - 2] * [http://acmp.ru/?main=task&id_task=157 ACMP…»

2014-08-25T14:16:40Z

Новая страница: «== Ссылки на задачи == * [http://acmp.ru/?main=task&id_task=156 ACMP #156 — Шахматы - 2] * [http://acmp.ru/?main=task&id_task=157 ACMP…»

Новая страница

== Ссылки на задачи ==

* [http://acmp.ru/?main=task&id_task=156 ACMP #156 — Шахматы - 2]
* [http://acmp.ru/?main=task&id_task=157 ACMP #157 — Карточки]
* [http://acmp.ru/?main=task&id_task=158 ACMP #158 — Великий комбинатор]

== Ссылки ==
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D0%BE%D0%BC%D0%B1%D0%B8%D0%BD%D0%B0%D1%82%D0%BE%D1%80%D0%BD%D1%8B%D0%B5_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D1%8B 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://informatics.mccme.ru/course/view.php?id=21 informatics.mccme.ru — Курс «Комбинаторные алгоритмы» — часть 1]

[[Категория:Комбинаторика]]