Изменения
→Оптимизация решения
Тогда динамика перепишется следующим образом: <br>
<tex>d'[mask] = 2^i</tex>, если <tex>|mask| = 1</tex> и <tex>mask[i] = 1</tex> <br>
<tex>d'[mask]=\sum_{j \in [0..n-1]} 2^i \cdot ((d[mask \oplus 2^i] \& M_i) \neq 0?1:0) </tex>, если <tex>|mask|> 1</tex> <br>
<tex>dp'[mask] = 0</tex> во всех остальных случаях <br>
Особое внимание следует уделить выражению <tex>d[mask \oplus 2^i] \& M_i</tex> . Первая часть выражения содержит подмножество вершин, для которых существует гамильтонов путь, заканчивающихся в соответствующих вершинах в подмножестве <tex>mask </tex> без вершины <tex>i</tex>, а вторая - подмножество вершин, связанных с <tex>i </tex> ребром. Если эти множества пересекаются хотя бы по одной вершине (их and <tex>\&</tex> не равен <tex>0</tex>), то, как нетрудно понять, в <tex>mask </tex> существует гамильтонов путь, заканчивающийся в вершине <tex>i</tex>.
Окончательная проверка состоит в сравнении dp<tex>d[2n 2^n - 1] </tex> c <tex>0</tex>.
Это решение использует <tex>O(2n2^n) </tex> памяти и имеет асимптотику <tex>O(2nn2^nn)</tex>.
== Реализация ==
