$ Динамика (28 октября 2014)

# Работа с множествами, как с целыми числами. Примеры на все операции.
## Биекция между числами 0..2^n-1 и подмножествами {0,1,...,n-1}
## Посмотреть i-й бит, присвоить i-й бит, обнулить i-й бит, множество всех элементов.
## Пересечение, объединение, разность. Проверка, содержится ли.
## Добавить к множеству элемент: +, \^, |
# Динамика по подмножествам
## Сумма на подмножестве: рекурсия, динамика
## Количество бит в числе, старший бит, перевернутая битовая запись
## Пример задачи: покрыть множество {0,1,...,n-1} минимальным числом множеств из набора A_1,...,A_m
# Задача: покрасить вершины графа в минимальное число цветов 
## Предподсчет good[A] за O(2^nn^2). Решение за O(4^n). 
## Перебор всех {под/над}множеств всех множеств циклами for за O(3^n), решение нашей задачи за O(3^n + 2^nn^2).
## Замена O(2^nn^2) на O(2^n) (good[] - динамика).
## Бонус: описание решения за O(2.44^n).
# Гамильтонов путь и цикл
## Определения.
## Решение задачи про путь за O(2^nn^2) времени и O(2^nn) памяти is[A, v] → is[A|2^x,x].
## Сводим задачу про цикл к задаче про путь.
## Улучшаем память до 2^n (битовый массив, минимальное изменение кода) end[A] |= 2^v.
## Улучшаем время до 2^nn (пересекается ли adj[x] c end[A\^2^x])