插头 DP

参考资料

插头 DP（轮廓线 DP）在网格图上逐格转移，以「轮廓线」上各列的连通性（插头）作为状态，常用最小表示法或括号序列编码连通块。它擅长解决回路 / 路径计数、网格覆盖等与连通性相关的问题。

在 $n\times m$ 的棋盘上，部分格子可走，求经过所有可走格子恰好一次的哈密顿回路的数量。