Динамика по профилю - общая теория

1. Матрица переходов С[2ⁿ][2ⁿ]
2. Предподсчет множества ребер
3. Возведение матрицы в степень (h=5, w=10⁹)
4. изломаный профиль
5. Рекурсивная реализация динамики по профилю (перебор + отсечение)
6. Обобщение динамики по профилю - число паросочетаний в произвольном графе.

Динамика по профилю - типы задач

1. Всякие "симпотичные узоры", "замощения доминошками"
2. Шахматы (конь, король)
3. Появляется связность (число гамильтоновых путей на решетке, число способов разбить на 2 связные фигуры)
4. Не решетки: треугольное поле, число способов замостить связными фигурками из не более 4 клеток

Практика

1. 101117a1 : A
2. 101117a1 : B
3. informatics.mccme.ru 1
4. informatics.mccme.ru 2
5. timus : 1519