%\author{Севастюк Дмитрий}
%\date{16 ноября 2015}
\Section{Больше динамики по подмножествам}{30 октября}{Севастюк Дмитрий}

\Subsection {Старший бит}

Найти старший бит числа от 0 до $2^n-1$.\\

a) Посчитать для всех. up[i] - старший бит числа i. $\O(2^n)$.
\lstinputlisting{sevastuk/a.cpp}

b) Только для X. $\O(\log X)$.
\lstinputlisting{sevastuk/b.cpp}

\Subsection{Независимость}

\begin{Def}
	Независимое множество - такое множество вершин графа, что\\
	никакие 2 вершины из этого множества не соединены ребром.
\end{Def}

Для каждого множества вершин проверить, правда ли, что оно независимо.\\

is[A] - независимость множества с маской A, up - вершина в A с наибольшим номером,\\
g[A] - соседи вершины up. A независимо, если A \ up независимо и из up в A нет рёбер, то есть\\
is[A] = (is[A\textasciicircum (1 $<<$ up)] \&\& ((g[up] \& A) == 0)).

\Subsection{Сумма на подмножестве, рекурсивная версия}

go - рекурсивная процедура, которая перебирает все множества и в процессе добавления элемента в множество пересчитывает сумму. Глубина рекурсии - n. Время - то же $\O(2^n)$.\\
i - номер элемента, A - текущее множество, S - текущая сумма.

\lstinputlisting{sevastuk/c.cpp}

Минус - рекурсия даёт большую константу. Плюс - не нужно хранить все суммы.\\
Из-за меньшего объёма используемой памяти с большими данными будет работать быстрее.

\pagebreak

\Subsection{Set Cover (аналог Рюкзака)}

Дано большое множество A и k его подмножеств B$_1$, B$_2$, ..., B$_k$.\\
Нужно представить A в виде объединения минимального количества каких-то B.\\

Пусть в A m элементов. Можно рекурсией аналогично предыдущей задаче за $\O(2^k)$.\\
А можно за $\O(2^m k)$. f[i, C] - количество множеств из первых i, которыми можно покрыть C.\\
relax(f[i + 1, C], f[i, C]) - когда не берём B$_i$, relax(f[i + 1, C | B$_i$], f[i, C]) - когда берём B$_i$.\\

\Subsection{Динамика по надмножествам}

\lstinputlisting{sevastuk/d.cpp}

1) Любое B - надмножество соответствующего A. $B = ... | A \supset A$.

2) Для одного A каждое следующее B больше предыдущего. B = (B + 1) | ... $\geq$ B + 1 > B.

3) Корректность. Для каждого A соответствующие ему B - ровно все его надмножества:\\
Пусть A$_1$, ..., A$_s$ - реальные упорядоченные по возрастанию (битовых масок) надмножества A.\\
Тогда посмотрим, как из A$_i$ получается A$_{i + 1}$. Разделим A$_i$ на старшие и младшие биты так, чтобы старшие заканчивались на 0, а все младшие были равны 1. Теперь разделим A и A$_{i +1}$ на старшие и младшие биты так, чтобы их количества совпадали. Грубо говоря, выбрали у A, A$_i$ и A$_{i + 1}$ одинаковые хвосты так, чтобы у A$_i$ хвост был максимальным из состоящих только из единиц. Тогда старшие биты у A$_{i + 1}$ такие же, как у A$_i$, только последний из них - 1, а не 0, иначе A$_{i + 1}$ не было бы больше, чем A$_i$. При этом младшие биты A$_{i + 1}$ (хвост) такие же, как у A, иначе A$_{i + 1}$ не было бы минимальным включающим A из множеств с такими старшими битами. Заметим, что это в точности соответствует методу выбора следующего B из цикла:\\
A$_{i + 1}$ = (A$_i$ + 1) | A. A$_i$ + 1 обеспечивает правильные старшие биты, а | A - правильные младшие.

4) Время - $\O(3^n)$. Заметим, что у каждого элемента на любом шаге может быть одно из трёх состояний: он в A (и, соответственно, в B); он не в A, но в B; он не в A и не в B. Значит, всего комбинаций состояний $3^n$, то есть будет сделано $3^n$ шагов.\\

Если мы умеем перебирать подмножества, то умеем и перебирать надмножества:\\
Для любого B надмножества A: (Всё $\setminus$ B) - подмножество (Всё $\setminus$ A). И наоборот.\\

Кроме того, если в множестве A m элементов, то у A ровно $2^{n - m}$ надмножеств.

\pagebreak

\Section{Динамика по скошенному профилю}{30 октября}{Севастюк Дмитрий}

\Subsection{Разбиение доски на доминошки}

Дана доска со сторонами W и H. Посчитать количество способов разбить её на доминошки.

\lstinputlisting{sevastuk/e.cpp}

Возвращаемое значение - количество способов покрыть всё оставшееся доминошками.\\
A - массив покрытости клеток. M - хэш таблица, в которой храним ответы.\\
Рекурсивный перебор за $\O(2^\frac{H W}{2})$. Идем по строкам. Покрываем клетку (x, y).

1) Если дошли до конца строки - переходим на следующую.

2) Если строки закончились - конец. Покрыть ничто можно одним способом.

3) Если клетка уже покрыта - возвращаем результат для следующей.

4) Если есть свободная клетка справа, то можно поставить горизонтальную доминошку:\\
Считаем клетки этой доминошки покрытыми, запускаем рекурсию, освобождаем клетки.

5) Если есть свободная клетка снизу, то можно поставить вертикальную доминошку:\\
Аналогично.

*) Если проверять, посчитано ли уже это значение, то  будет не перебор, а (ленивая) динамика по профилю, которая работает уже за $\O(2^W H W)$.\\

Про M:

1) Можно хранить весь A как число (бит - покрытость клетки), если $W \cdot H \leq 128$ (\_\_int128).

2) A - vector$<$vector$<$int$>>$, M - map$<$vector$<$vector$<$int$>>$, int$>$.

3) M[A][x][y] или tuple<\_\_int128, int, int>. Полиномиальный хэш.

\pagebreak

\Subsection{Красивые матрицы}

\begin{Def}
	Красивая матрица - матрица, в которой нет квадрата 2х2 из нулей.
\end{Def}

Есть длинная матрица $5 \cdot 10^9$ из нулей и единиц. Сколько в ней красивых матриц?\\

Динамика. f[i,C] - сколько способов заполнить оставшуюся часть матрицы, если уже заполнено i столбцов, причём последний из них - C. is[C$_1$, C$_2$] - можно ли после столбца C$_1$ поставить столбец C$_2$. Считаем количество матриц, в которых за i-м столбцом C$_1$ следует i+1 -й C$_2$, если до i включительно всё посчитано.\\
f[i + 1, C$_2$] = $\sum\limits_{C_1}$(f[i, C$_1$] $\cdot$ is[C$_1$, C$_2$]), то есть f[i + 1] = f[i] $\cdot$ is для матриц f и is.\\
f[$10^9$] = f[0] $\cdot$ (is$^{(10^9)}$), а это можно сделать за $(2^5)^3 \cdot \log_2 10^9$ ($2^5$ - размер матрицы is).