插头 DP
定义
基于连通性状态压缩的 DP.
一个方向的插头存在表示这个格子在这个方向可以与外面相连。
状态
一个 \(n \times m(n, m \le 12)\) 的棋盘，有的格子是障碍，问共有多少满足要求的回路？
本题中，所有非障碍格子一定是从一个插头进、一个插头出，刚好用两个插头，方案数为 \(C_4^2=6\) 种.
- 按照从上到下的顺序依次考虑每一行。
- 分析第 \(i\) 行那些信息对第 \(i+1\) 行有影响，记录第 \(i\) 行的每个格子是否有下插头，这决定了第 \(i+1\) 行的每个格子是否有上插头。
- 给每个格子标记一个数，同一个连通块标记相同的数，比如 \({2, 2, 1, 1}\) 表示格子 \(1, 2\) 和 \(3, 4\) 分别在两个连通块内。通常使用最小表示法对格子进行标记。
- 一种最小表示法为：所有的障碍格子标记为 \(0\)，第一个非障碍格子以及
优化
转移
假设从第 \(i\) 行转移到第 \(i+1\) 行，可以枚举第 \(i+1\) 行的每个格子的状态，对于任何一个非障碍格子，它是否有上插头和左插头已知，因此最多只有两种情况，状态的转移数 \(\le 2^n\).
逐格递推
转移
