ripatti 5 мая в 12:49

Винтик и Шпунтик, часть 1: формула включений-исключений

Средний

14 мин

1.6K

Туториал

Винтик и Шпунтик договариваются о стратегии

В данной серии статей я изложу мои наработки по решению задачи про Винтика и Шпунтика в рамках челленджа @vvvphoenix. Наработок достаточно много, и изложение их всех в одной статье получилось бы слишком объемным, либо же пришлось описывать всё достаточно сжато. Ни того, ну другого не хотелось бы, поэтому разбиваю изложение на части. Пока планируется 4 части, возможно в ходе их написания появятся идеи для новых частей или новые продвижения в решении задачи. И тогда частей будет больше. Данная первая часть скорее вводная, в которой я опишу такой подход к подсчету числа вариантов в различных комбинаторных задачах, как "формула включения-исключения".

Описывать все буду достаточно подробно с самого начала, чтобы было понятно даже людям не совсем "в теме". Однако, такие подробности не только для читателей, сколько для себя. Для того, чтобы разложить у себя в голове всё последовательно и по полочкам. И ничего не пропустить.

Постановка задачи и совершенные паросочетания

Формулировка задачи в редакции челленджа звучит следующим образом:

«Незнайка записывает 9 разрядов 10-значного десятичного числа и пропускает один по своему выбору. Пропущенный разряд он предлагает записать Винтику, а затем показывает полученное 10-значное число Шпунтику. Сколькими способами могут Винтик и Шпунтик договориться, чтобы Шпунтик угадал, какой именно разряд записал Винтик?»

Предполагается, что Винтик и Шпунтик договариваются заранее, до того как Незнайка показывает Винтику число с пропущенным знаком, при этом зная "правила игры". То есть на каждый вариант числа с пропуском, которое может показать Незнайка, у Винтика должен быть такой вариант заполнения пропуска, чтобы потом Шпунтик, глядя на получившееся число уже без пропуска, смог однозначно установить, в каком месте был пропуск.

Давайте разберёмся с "ослабленной" версии задачи, когда Незнайка записывает всего лишь 2-значное число с пропуском (в двоичной системе счисления). Варианты того, что мог записать Незнайка:,,,. Всего 4 варианта. Винтик может переделатьлибо в, либо в.— либо в, либо в. И так далее. Варианты того, что может сделать Винтик в каждом из случаев, можно нарисовать в виде двудольного графа, где каждая вершина в левой доле соответствует тому, что написал Незнайка, а в правой — тому, во что это может превратить Винтик. Причём рёбра в этом графе — варианты действий Винтика.

Теперь, после заполнения пропуска, Шпунтику доступен один из вариантов,,,. И по нему Шпунтику нужно определить какое число с пропуском было изначально. Причем он может выбирать только между теми вариантами, откуда из левой доли приходят рёбра.

Заметим, что в обоих долях вершин поровну, поэтому чтобы Шпунтику не ошибиться (с каким бы числом с пропуском не пришел Незнайка), на любые два варианта, что видит Шпунтик, ответы должны быть различны. Действительно, если на какие-то два "входа" для Шпунтика соответствуют одной и той же вершине слева, то какая-то вершина слева вовсе не будет "покрыта" возможными ответами Шпунтика. И как быть, если Незнайка запишет именно этот не покрытый вариант? Если же для любых двух "входов" для Шпунтика ответы различны — то любой вариант, с каким бы не пришел Незнайка, будет покрыт, и Шпунтик его угадает. Дело осталось за малым: Винтику и Шпунтику нужно договориться так, чтобы Винтик вставлял цифру в соответствии с "табличкой" всевозможных ответов Шпунтика.

В общем и целом, для Винтика и Шпунтика необходимо и достаточно какое-то взаимно-однозначное соответствие между вершинами левой и правой доли графа, причём каждую пару вершин в этом соответствии должно соединять ребро графа. Такая конструкция называется совершенным паросочетанием. Совершенными они называются потому, что покрывают все вершины графа. Ну и количество способов договориться — это количество таких попарно различных паросочетаний. Например, для нашего "ослабленного" бинарного случая совершенных паросочетаний ровно два:

В общей, не "ослабленной", постановке задачи у нас и в левой, и в правой долях по $10^{10}$ вершин. Для промежуточных (так называемых-арных) версий задачи у нас в обеих долях по N^N вершин. Бинарный и тернарный варианты задачи решаются достаточно легко, как показал сам @vvvphoenix. А вот уже с кватернарным случаем возникают проблемы.

Количество совершенных паросочетаний и перманент

В принципе, задачу можно попытаться решить перебором: для каждой вершины левой доли выберем исходящее ребро всеми возможными способами, а затем проверим, что все вершины правой доли покрыты ровно одним ребром. Получим решение за $O^*(N^{N^N})$ (здесь и далееозначает $O(f(n) \cdot Poly(n))$ , где Poly(n) — какой-то полином от). Даже для N=3 получается астрономическая сложность. Впрочем, в перебор вариантов можно добавить некоторые отсечения: например, откатываться, как только какая-либо вершина из правой доли покрыта двумя выбранными ребрами. Тогда случай N=3 можно решить очень быстро, но для большихвозникнут сложности: если мы будем перечислять все варианты, то нам в любом случае потребуется количество операций не меньше, чем количество вариантов.

Однако, чтобы найти ответ, можно не перечислять все варианты по одному. Один из вариантов так сделать: динамическое программирование.

Обозначим множество вершин левой доли графа за, а правой — за. Пустьдля $X \subseteq R$ — количество частичных паросочетаний, которые полностью покрывают |X| первых вершин левой доли(для этого вершины левой доли надо заранее пронумеровать: $l_1, l_2, \ldots , l_{|R|}$ ) и все вершины виз правой доли. Тогда $dp( \not O ) = 1$ (упс) и

$dp(X) = \sum_{\substack{r \in X \\ (l_{|X|}, r) \in E}} dp(X \setminus \{ r \})$

Суть формулы достаточно проста: мы всеми способами убираем "последнее" ребро из, сводя задачу к чуть меньшей по размеру. Ответ — это dp(R) . Итого получаем решение за $O^*(2^{N^N})$ , что заметно быстрее перебора. Единственный недостаток этого решения — нам нужно $O(2^{N^N})$ памяти для хранения состояний. Хорошая новость состоит в том, что есть решение, лишенное данного недостатка — это формула включений-исключений, о которой чуть ниже.

Также немного упомянем такую штуку, как перманент. Построим матрицу, в которой на пересечении-й строки-го столбца будет, если-я вершина левой доли и-я вершина правой доли соединены ребром. То есть матрица— это такой компактный способ записать ребра двудольного графа. Например, для нашего случая N=2 матрица выглядит следующим образом:

$A = \left( \begin{matrix} 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{matrix} \right)$

По сути эта та самая "табличка Шмелёва" из публикации @vvvphoenix. Перманент матрицы находится по следующей формуле (полагая, чтоимеет размер $n \times n$ ):

$\mathbf{perm} A = \sum_{\sigma \in S_n} \prod_{i=1}^n A_{i,\sigma_o}$

Мы перебираем все перестановки $\sigma$ , которые по сути соответствуют всевозможным совершенным паросочетаниям в полном двудольном графе, а затем суммируем веса всех этих паросочетаний. Здесь вес паросочетания — это произведение весов ребер, которые берутся из матрица. Таким образом, если паросочетание действительно допустимое для матрицы(все ребра "на месте" с весом), то к сумме прибавится. Иначе, если хотя бы одного ребра нет — вес паросочетания будет равен.

Проблема в том, что для произвольных матриц (и даже для 0,1 -матриц) перманент быстро (за полиномиальное время) считать никто не умеет. Его можно вычислить по определению выше за O^*(n!) , однако есть способ чуть быстрее — через то же самое динамическое программирование за O^*(2^n) , что описано выше. Разве что формула чуть-чуть изменится:

$dp(X) = \sum_{r_i \in X} A_{|X|,i} \times dp( X \setminus \{ r_i \} )$

Отметим, что эта формула работает для любых матриц, не обязательно состоящих только из 0 и 1. В любом случае, вот эти матрицы и перманент — это просто еще одна формулировка изначально задачи, и к решению самой задачи нас не сильно приближает.

Формула включений-исключений и её доказательство

Применительно к нашей задаче решение через формулу включения-исключения описывается в слайдах лекции по ссылке. Саму лекцию я не видел, поэтому восстановлю тут необходимую нам информацию по имеющимся картинкам.

Слайд с формулой включений-исключений (и с её доказательством) следующий:

Формула включений-исключений и её доказательство

У нас просто есть две какие-то функциии g(X) , которые возвращают какие-то числа для каждого подмножества $X \subseteq A$ . При этом f(X) можно выразить через g(X) согласно формуле на слайде. Тогда, как утверждает Лемма, мы можем обратить вычисление функций: наоборот, выразить g(X) через f(X) .

Когда это может кому-то понадобиться? Например, в случаях, когда g(X) считается долго, сложно и неясно как (и именно её нам надо посчитать для решения задачи), а вот f(X) решается просто, быстро и понятно.

Теперь перейдём к доказательству. Первый переход в доказательстве — это просто подстановка выражения функциичерез функцию. Во втором переходе мы группируем все слагаемые по входящему туда множителю g(Z) , после чего в каждой группе выносим этот множитель за скобку. Третий переход самый сложный для понимания. Там утверждается (в сноске ниже), что все слагаемые (кроме g(Z) при Z=X ) будут нулевые. Проиллюстрируем этот момент картинкой:

Итак, если $Z \ne X$ , то мы берем сумму по всем множествам, "зажатым" междуи. В частности, слагаемых в сумме $2^{|X-Z|}$ . Давайте возьмём в "зазоре" междуикакой-нибудь элемент. Тогда всевозможные множестваможно разбить на пары. В каждой паре множества Y_1 и Y_2 почти одинаковы, единственное отличие: в Y_1 входит, а в Y_2 — нет. То есть, $Y_1 = Y_2 \cup \{ v \}$ . Одно из этих множеств будет давать вклад в общую сумму, а другое, то есть итоговый вклад. И так по всем парам.

В случае Z = X слагаемое в сумме по "зажатым"оказывается ровно одно, и оно равно. Именно благодаря ему до самого конца "доживает" единственное слагаемое внешней суммы g(X) .

Применение формулы к нашей задаче

Теперь нам нужно подобрать подходящие функции f(X) и g(X) , которые можно "приложить" к нашей задаче. Мы будем рассматривать покраски рёбер двудольного графа следующего вида: для каждой вершины из левой долимы будем выбирать ровно одно исходящее из неё ребро и красить его в красный цвет. При этом в некоторые вершины правой долив итоге могут входить несколько покрашенных рёбер, а некоторые — ни одного. Доли графа равномощны, то есть |L| = |R| , и в каждой раскраске у нас будет покрашено в красный цвет ровно |R| рёбер.

Примеры покраски рёбер какого-то двудольного графа

Будем называть вершинуиз правой долипокрытой, если в неё входит хотя бы одно покрашенное ребро. Аналогично, будем называть вершину не покрытой, если в неё не входит ни одного покрашенного ребра.

Теперь для каждого подмножествавершин правой долиопределим функцию g(X) как количество раскрасок рёбер (вида, описанного выше), в которых все вершины изпокрыты, а все вершины не их(то есть из $R \setminus X$ ) — не покрыты.

Соответственно, для каждого подмножества $X \subseteq R$ определим функцию f(X) как количество допустимых раскрасок, в которых все вершины не изне покрыты (некоторые вершины изпри этом могут быть покрыты, а остальные — не покрыты).

Несложно убедиться, что $f(X) = \sum_{Y \subseteq X} g(Y)$ . Действительно, рассмотрим все допустимые раскраски, которые считает f(X) , а затем сгруппируем их: в каждой группе будут все способы, в которых множество покрытых вершин правой доли в точности равно (а остальные вершины изне покрыты). Но количество раскрасок в каждой такой группе— это в точности g(Y) .

Ответом на нашу задачу будет . И вот почему. В каждой раскраске, которую учитывает g(R) , будут учтены все те способы, в которых все |R| вершин из правой доли покрыты. Но у нас в каждой раскраске ровно |R| покрашенных рёбер. Значит каждая вершина правой доли будет покрыта ровно одним красным ребром. А это, собственно, означает, что рассматриваемые раскраски функцией g(R) являются паросочетаниями.

Отлично, теперь мы можем через формулу включений-исключений выразить g(R) через знакопеременную сумму значений f(X) . Как считать f(X) ? А очень просто.

Пусть дано— это множество "разрешённых" вершин, куда можно проводить покрашенные рёбра (а можно и не проводить). А вот вершины множества $R \setminus X$ — "запрещённые". Туда нельзя проводить покрашенные рёбра ни при каких обстоятельствах.

Теперь мы считаем количество покрасок так: для каждой вершины левой доли (из) мы смотрим во сколько разрешённых вершин правой доли мы можем провести ребро. Это, собственно, количество способов покрасить исходящее ребро из данной вершины левой доли. Теперь просто перемножаем эти количества способов. Это и есть значение f(X) .

Например, пусть для графа, показанного на картинке, мы считаем f(X) , где $X = \{r_1, r_2\}$ . То есть первые две вершины правой доли разрешённые, а третья — запрещённая. Тогда для первой вершины левой доли имеетсяисходящих ребра, которые можно красить. У второй вершины левой доли — тоже, а у третьей — только одно. Итого получаем $f(X) = 2 \cdot 2 \cdot 1 = 4$ , этиварианта показаны на картинке внизу.

Включения и исключения глазами скульптора

Мы же будем брать все способы и затем выкидывать лишние

Формулу включений-исключений можно доказать по-другому. Для удобства дальнейшего изложения введем функцию $\overline{f}(X) = f( R \setminus X )$ . Здесьбудет задавать множество вершин правой доли, которые нельзя покрывать. Также введем значения Q_i дляотдо |R| , которые будут обозначать количество способов раскраски рёбер, в которых первыевершин правой доли покрыты. $Q_{|R|}$ — это то, что мы ищем.

Очевидно, $Q_0 = \overline{f}( \not O )$ . Также довольно ясно, что $Q_1 = \overline{f}( \not O ) - \overline{f}( \{ r_1 \} )$ . Действительно, мы из всех способов вычитаем все те, в которых r_1 не покрыта, и у нас остаются только те способы, где r_1 покрыта. Это можно изобразить следующей картинкой:

Как теперь вычислить Q_2 ? Надо из Q_1 вычесть все те варианты, когда вершина r_1 покрыта, а вершина r_2 — нет. Это вон тот верхний синий прямоугольник на картинке. Как посчитать эти варианты? Да точно так же, как и Q_1 , нужно только везде в множества добавить r_2 . Получим:

$Q_2 = Q_1 - \left(\overline{f}( \{ r_2 \} ) - \overline{f}(\{r_1, r_2\})\right) = \overline{f}( \varnothing ) - \overline{f}(\{r_1\}) - \overline{f}( \{ r_2 \} ) + \overline{f}(\{r_1, r_2\})$

Теперь введём в рассмотрение третью вершину r_3 . Картинка теперь станет трёхмерной, и нам нужно из текущего числа способов вычесть вон те в дальнем "кубике":

Может диаграммами Эйлера-Венна было бы нагляднее...

Формулу выписывать не буду, но нам нужно просто взять Q_2 , везде в множества добавить r_3 , после чего полученную сумму вычесть из Q_2 — и получится Q_3 . Проделав эту процедуру |R| раз, получим:

$Q_{|R|} = \sum_{X \subseteq R} (-1)^{|X|} \overline{f} (X) = \sum_{X \subseteq R} (-1)^{|R|-|X|} f(X)$

Это совпадает с формулой, полученной выше.

Плюс данного доказательства в следующем: числа Q_i мы получаем в порядке убывания, так как все способы, соответствующие $Q_{i+1}$ , входят также в множество способов, соответствующих Q_i . Это позволяет оценивать финальный ответ, посчитав формулу включений-исключений лишь частично. Да, есть способы оценивать ответ точнее, но здесь мы получаем оценку "нахаляву", всего лишь аккуратно выбрав порядок суммирования.

Обобщение "классической" задачи

Давайте напоследок сделаем обобщение изначальной задачи. Для того, чтобы было больше вариантов "входных данных". Решения для обобщений задачи могут в будущем дать какие-нибудь подсказки к решению изначальной задачи.

Будем рассматривать числа с переменной системой счисления. Например, пусть в числе x_1x_2x_3 первая цифрабудет приниматьразличных значений,—различных значений, а—различных значений. Тогда всего всевозможных чисел у нас будет $a_1 \cdot a_2 \cdot a_3$ .

Примером "чисел" с переменной системой счисления для различных разрядов является запись текущего времени, например 12:13:14. При этом старший "разряд" часов может приниматьразличных значений, а другие два "разряда" минут и секунд по.

Итак, пусть количество способов для каждой из"цифр" числа задано последовательностью $(a_1, a_2, \ldots, a_n)$ . Тогда общее количество всевозможных чисел равно $P = a_1 \cdot a_2 \cdot \ldots \cdot a_n$ . Теперь посчитаем количество чисел, в которых в некоторых разрядах стоят звёздочки. Если звёздочка стоит в первом (старшем) разряде, то количество таких чисел равно $a_1 \cdot a_2 \cdot \ldots \cdot a_n = P / a_1$ . Аналогично, если звездочка стоит в-м разряде, то количество чисел равно P/a_i . Итого, если P^* — это общее количество "звезданутых" чисел, то

$P^* = \dfrac{P}{a_1} + \dfrac{P}{a_2} + \ldots + \dfrac{P}{a_n}.$

Нас интересуют варианты задачи, где P = P^* , чтобы количество вершин в долях графа было одинаково и паросочетания были совершенными (дляответ очевидно равен, а для случая P > P^* паросочетания получатся не совершенные, и нужно еще договориться с тем, что же считать для Винтика и Шпунтика "стратегией"). Итак, заменяя P^* на формулу выше и сокращая обе части равенства на, получаем

$1 = \dfrac{1}{a_1} + \dfrac{1}{a_2} + \ldots + \dfrac{1}{a_n}.$

Так это же египетские дроби! "Классическому" варианту задачи соответствует сумма издробей, каждая из которых равна 1/N , и эта сумма действительно равна. Будем записывать такие задачи в виде последовательности $(N, N, \ldots, N)$ . Для n=2 у нас есть только классическая задача (2,2) . Для n=3 помимо классической (3,3,3) можно ввести в рассмотрение также задачи (2,4,4) и (2,3,6) . Для n=4 ...

А теперь давайте, чтобы создать какую-то активность в комментариях, рассмотрим следующие задачки, одну из которых я нашел в интернете в списке задач для кружка 7 класса, загуглив словосочетание "египетские дроби". Остальные мои задачки логично вытекают из неё.

Докажите, что при каждомуравнение
$\dfrac{1}{x_1} + \dfrac{1}{x_2} + \ldots + \dfrac{1}{x_n} = 1$
в натуральных числах имеет конечное число решений.
Придумайте алгоритм генерации всех таких решений для заданного. Не обязательно, чтобы алгоритм был супер эффективным, но нужно чтобы он находил все решения.
Найдите все решения для.

Решения пишите в комментариях, в следующей части я напишу свои решения. Как раз решения уравнения для n=4 и будут составлять "бенчмарк" для тестирования последующих улучшений алгоритма решения изначальной классической задачи Винтика и Шпунтика.

Пример кода

Я набросал пример кода для трехзначных чисел на языке Python. Его можно видеть ниже:

def solve_vs( A, B, C ):
	# build graph
	L = []
	for i in range(A):
		for j in range(B):
			for k in range(C):
				L.append( [i, j, k] )
	R = []
	for j in range(B):
		for k in range(C):
			R.append( [-1, j, k] )
	for i in range(A):
		for k in range(C):
			R.append( [i, -1, k] )
	for i in range(A):
		for j in range(B):
			R.append( [i, j, -1] )
	G = []
	for x in L:
		adj = []
		for i in range(len(R)):
			flag = True
			for j in range(3):
				if x[j]!=-1 and R[i][j]!=-1 and x[j]!=R[i][j]:
					flag = False
			if flag: adj.append( i )
		G.append( adj )

	# calc formula
	ans = 0
	k = 0
	last_ans = 0
	for s in range((1<<len(R))-1,-1,-1):
		if k<len(R) and ((s>>k)&1)==0:
			print( "subtotal", k, ans, file=sys.stderr )
			print( "subtotal", k, ans, last_ans/ans, flush=True )
			last_ans = ans
			k += 1
		prod = -1 if (((1<<len(R))-1-s).bit_count()&1) else 1
		for adj in G:
			sum = 0
			for u in adj:
				if ((s>>u)&1):
					sum += 1
			prod *= sum
		ans += prod
	print( "total", ans )

solve_vs( 3, 3, 3 )

Первая половина кода отвечает за построение графа. Сначала мы формируем числа, соответствующие вершинам левой и правой долей. Храним их в виде списков "цифр", звёздочку обозначаем как "-1". Граф хранится в виде списков смежности для вершин левой доли.

Далее вычисляем ответ по формуле. Вперебирается подмножество вершин правой доли. При этом единичный бит означает, что соответствующую вершину правой доли можно покрывать (а можно не покрывать), а нулевой бит — что данную вершину покрывать нельзя. Количество способов провести ребро для каждой вершины левой доливычисляется как количество "разрешенных" вершин правой доли, куда есть ребро из. Мы перемножаем все эти способы по всем вершинам левой доли и прибавляем к ответу (или вычитаем, в зависимости от четности количества нулей в).

Как только все комбинации для каких-нибудьпоследних битовбудут обработаны — мы выводим промежуточный ответ. Это именно те приближения к финальному ответу, которые обсуждались в разделе про скульптора.

В результате работы программы (скажем прямо: не быстрой) получились следующие ответы:

Задача	Ответ	Разложение на простые
		$2^9 \cdot 3 \cdot 7$
		$2^9 \cdot 3^2 \cdot 5$
		$2^{10} \cdot 3^2 \cdot 5$

Интересное наблюдение: ответ для (2,4,4) ровно в два раза меньше, чем для (2,3,6) . Совпадение или закономерность? Кто знает...

Полные логи программы для каждого случая можно посмотреть под спойлерами:

(3, 3, 3)

subtotal 0 7625597484987 0.0
subtotal 1 5366161193139 1.4210526315789473
subtotal 2 3776187506283 1.4210526315789473
subtotal 3 2657317134051 1.4210526315789473
subtotal 4 1869963909147 1.4210526315789473
subtotal 5 1315900528659 1.4210526315789473
subtotal 6 926004075723 1.4210526315789473
subtotal 7 651632497731 1.4210526315789473
subtotal 8 458556202107 1.4210526315789473
subtotal 9 322687697779 1.4210526315789473
subtotal 10 193593800315 1.6668286755771566
subtotal 11 116144990275 1.6668286755771566
subtotal 12 69680220875 1.6668286755771566
subtotal 13 40148676475 1.735554618304513
subtotal 14 23133052715 1.735554618304513
subtotal 15 13328910811 1.735554618304513
subtotal 16 7218187044 1.8465732087227413
subtotal 17 3908963376 1.8465732087227413
subtotal 18 2116874304 1.8465732087227413
subtotal 19 878041080 2.410905767643582
subtotal 20 339434928 2.586772920434399
subtotal 21 118398672 2.866881209613567
subtotal 22 40756224 2.9050451778849777
subtotal 23 12553776 3.246531083556055
subtotal 24 3287856 3.8182256157203964
subtotal 25 724464 4.53832902670112
subtotal 26 118848 6.095718901453958
total 10752

(2, 4, 4)

subtotal 0 1853020188851841 0.0
subtotal 1 1029455660473245 1.8
subtotal 2 571919811374025 1.8
subtotal 3 317733228541125 1.8
subtotal 4 176518460300625 1.8
subtotal 5 98065811278125 1.8
subtotal 6 54481006265625 1.8
subtotal 7 30267225703125 1.8
subtotal 8 16815125390625 1.8
subtotal 9 9341736328125 1.8
subtotal 10 5189853515625 1.8
subtotal 11 2883251953125 1.8
subtotal 12 1601806640625 1.8
subtotal 13 889892578125 1.8
subtotal 14 494384765625 1.8
subtotal 15 274658203125 1.8
subtotal 16 152587890625 1.8
subtotal 17 90087890625 1.6937669376693767
subtotal 18 53187890625 1.6937669376693767
subtotal 19 31402130625 1.6937669376693767
subtotal 20 18539817921 1.6937669376693767
subtotal 21 9747221346 1.902061855670103
subtotal 22 5124555396 1.902061855670103
subtotal 23 2694210696 1.902061855670103
subtotal 24 1416468496 1.902061855670103
subtotal 25 581258496 2.4368994272730595
subtotal 26 225833712 2.573834042988232
subtotal 27 81758688 2.762198336646498
subtotal 28 27007968 3.027206193372267
subtotal 29 6994368 3.8613879052403304
subtotal 30 1517184 4.610098709187548
subtotal 31 246528 6.154205607476635
total 23040

(2, 3, 6)

subtotal 0 150094635296999121 0.0
subtotal 1 83385908498332845 1.8
subtotal 2 46325504721296025 1.8
subtotal 3 25736391511831125 1.8
subtotal 4 14297995284350625 1.8
subtotal 5 7943330713528125 1.8
subtotal 6 4412961507515625 1.8
subtotal 7 2451645281953125 1.8
subtotal 8 1362025156640625 1.8
subtotal 9 756680642578125 1.8
subtotal 10 420378134765625 1.8
subtotal 11 233543408203125 1.8
subtotal 12 129746337890625 1.8
subtotal 13 72081298828125 1.8
subtotal 14 40045166015625 1.8
subtotal 15 22247314453125 1.8
subtotal 16 12359619140625 1.8
subtotal 17 6866455078125 1.8
subtotal 18 3814697265625 1.8
subtotal 19 1861572265625 2.0491803278688523
subtotal 20 908447265625 2.0491803278688523
subtotal 21 443322265625 2.0491803278688523
subtotal 22 216341265625 2.0491803278688523
subtotal 23 105574537625 2.0491803278688523
subtotal 24 51520374361 2.0491803278688523
subtotal 25 20270311224 2.5416666666666665
subtotal 26 7975204416 2.5416666666666665
subtotal 27 3137785344 2.5416666666666665
subtotal 28 1234538496 2.5416666666666665
subtotal 29 485720064 2.5416666666666665
subtotal 30 191102976 2.5416666666666665
subtotal 31 77723072 2.4587676616796617
subtotal 32 28343168 2.7422154079600416
subtotal 33 8951040 3.1664664664664666
subtotal 34 2311680 3.872093023255814
subtotal 35 437760 5.280701754385965
total 46080

Можно видеть, как количество способов при каждом удвоении числа слагаемых формулы уменьшается. Числа в конце каждой строки означают отношение числа способов в предыдущей строке к числу способов в текущей. Эти отношения постепенно увеличиваются, то есть число способов уменьшается с характерным "свистом". То есть, с ускорением. Это все мы будем использовать для эвристической оценки ответа для задачи (4,4,4,4) .

Заключение

В этой части мы познакомились с формулой включений-исключений. Она даёт алгоритм решения задачи Винтика и Шпунтика за время $O^*(2^{N^N})$ , что значительно быстрее наивного перебора за $O^*(N^{N^N})$ , и уж тем более быстрее наивного вычисления перманента матрицы смежности двудольного графа за. Тем не менее, для N=4 мы получаем $2^{256}$ слагаемых в формуле, и вычислить их сумму (если считать "в лоб") за разумное время решительно невозможно. Однако мы рассмотрели самый общий подход, который работает вообще для любого двудольного графа (у которого доли равномощны). У нас же двудольный граф специального вида, и для него вычисление формулы можно ускорить как минимум до $O^*(2^{N^{N-2}(N+1)})$ , что для N=4 дает порядка $2^{80}$ операций. Это гораздо меньше $2^{256}$ , но подробности — в следующей части.