轮廓线 DP + 外部容斥。似乎是 CDQ 论文题。
有一个 \(n\times m\) 的矩形表格，其中有一些位置有障碍。现在要在这个表格内放一些 \(1\times2\) 或者 \(2\times1\) 的多米诺骨牌，使得任何两个多米诺骨牌没有重叠部分，任何一个骨牌不能放到障碍上。并且满足任何相邻两行之间都有至少一个骨牌横跨，任何相邻两列之间也都至少有一个骨牌横跨。求有多少种不同的放置方法，注意并不需要放满所有没有障碍的格子。\(n,m\le15\)。
-
轮廓线思维是经典的优化状压 DP 方法。相比于一次确定一行时不仅要枚举上行状态还要枚举当前行状态，轮廓线方法依次确定一行的每个位置 \(i\)，并且状压下上一行的 \((i,m]\) 和这一行的 \([1,i]\)（轮廓线）作为状态。把一次转移一层改为一次转移一步，做到 \(O(2^mm)\) 转移。
-
考虑一类问题的限制需要记录的状态过多，导致难于 DP。例如此题，障碍限制容易处理，但 DP 中处理行和列的限制要求存下之前所有行和列。所以考虑 外部容斥，就是 DP 中去掉部分限制得到结果，在外面枚举满足哪些限制，利用之前结果容斥计算。
-
在此题中，可以发现假设枚举了某 \(r\) 行和某 \(c\) 列不能跨过，整个图被分为至多 \((r+1)(c+1)\) 个矩阵内部分别填写，不能跨越矩阵边界。相当于只需要求 \(g_{i,j,l,r}\) 表示每个子矩阵内部不考虑行列限制填写的方案数，乘法原理计算，这个可以 DP 求出。
-
但是最后的容斥需要 \(O(2^{n+m}nm)\) 复杂度爆炸。考虑 外部容斥 中，我们只需要 去掉部分限制，例如此题 DP 中不能处理的仅是跨越列的限制，跨越行的限制可以利用状压处理。于是考虑改内层为 带容斥系数 DP（为了计算容斥系数，可以加一维状态 \(0/1\)）。外部只需要枚举哪些列满足限制即可。
-
也可以考虑不修改内层 DP，而是在中间再套一个 DP。也就是在 枚举了行的限制的前提下 DP 计算列的贡献和，相当于在 \(g\) 上做序列分段 DP（带容斥系数）。