T1. P4262 [Code+#3] 白金元首与莫斯科
\(n \times m\) 的棋盘上有一些障碍格，对于每一个非障碍格，需要求出若该格为障碍格，用 \(1 \times 2\) 的砖铺满棋盘的方案数。其中 \(1 \le n,m \le 17\)。
看到这一种比较抽象的网格上的题目，可以考虑使用插头 dp 来解决。
对于一个 \(1 \times 2\) 的方块，其实就是左插头连上右插头或者一个下插头拼一个上插头，那么可以考虑使用一个二进制来维护现在的轮廓线，然后暴力 Hash 维护即可。
对于求解每一格怎么样的问题，可以考虑正着反着各作一遍插头 dp，然后在把答案合并。
先考虑正着做，若当前非障碍格即没有左插头也没有上插头，就记录下对于当前格在当前轮廓线下的方案数总和。接着考虑倒着做，若当前格即没有右插头也没有下插头，就查一下正着做时的记录，然后把贡献扔进答案里。
标签：插头,格即,正着,times,2025,奉献者,先行者,障碍,考虑 From： https://www.cnblogs.com/Carousel/p/18679655