轮廓线 dp
泛化ψ(｀∇´)ψ
就是对于棋盘和连通类的状压 dp 问题，我们通常是按行考虑的。
这样表达状态并不是很爽，而且转移复杂度会比较高，有时候我们可以考虑换一种策略：按格子转移。
具体来说我们考虑维护一个叫轮廓线的东西，就是说前一半是这一行的状态，后一半是上一行的状态，然后在拐点处考虑转移，相当于是把状态一个一个“按下来”
类似这样：
我们转移就是考虑绿色格子的转移，转移过后绿色格子推进一个，粉色被按下来一个变成蓝色。
适用条件大概就是你发现状态可以全部归约到格子转移，而且状态可以分层的这种。
例题ψ(｀∇´)ψ
UVA11270 Tiling Dominoesψ(｀∇´)ψ
用 \(1\times 2, 2\times 1\) 的骨牌覆盖一个 \(n\times m\) 的网格。
\(n\times m \le 100\)。
状压 dp 的部分提过，这个就是那个莫德里安的梦想，但是数据范围拉大了。
我们回顾一下状压 dp 做法怎么做，考虑 \(dp(i, msk)\) 表示考虑到第 \(i\) 行，当前行状态为 \(msk\) 的方案数。
\(msk\) 的每一位表示骨牌的状态，如果这一位为 \(1\) 说明这一位使用了一个 \(2\times 1\) 的上部覆盖。
转移就考虑预处理一下能够相互转移的合法状态，也就是按位或之后不存长度为奇数的 \(0\) 连通块。
不妨记 \(n\) 为行数， \(n > m\)，另外的可以转九十度，状态数是 \(O(n2^m)\) 的，然后暴力转移的时间复杂度是 \(O(nm2^{2m})\) 的，可以 \(O(m2^{2m})\) 预处理，优化一下常数。
这样是无法通过本题的数据的，我们考虑按格而不是按行 dp，也就是考虑 dp 转移的轮廓线。
考虑设 \(dp(i, j, msk)\) 表示，考虑第 \(i\) 行第 \(j\) 列，当前轮廓线状态为 \(msk\) 的方案数，但是这里的 \(msk\) 就表示简单的，是否被覆盖了，具体原因下面会说。
其中对于 \(msk(k)\)，如果 \(k \le j\)，那么它表示当前行的状态。
如果 \(k > j\)，那么它表示上一行的状态，然后我们考虑转移。
相当于是考虑格子 \((i, j)\) 应该被赋成什么，分类讨论：
一种就是考虑放一个竖着的骨牌的下部，这要求上方是没有被填过的格子。
还有一种就是考虑放一个横着的骨牌的右部，这要求左方没有被填过的格子。
最后一种就是什么都不干，等着上面两种情况来把它填满。
每次转移从 \(dp(i, j - 1, msk)\) 转移过来就行。
这种转移方式相较于正常的状压 dp 不太一样，状压 dp 那样设计的原因是，我们没有办法直接用是否被填来描述骨牌的转移。
而轮廓线 dp 则是考虑按格转移，且左方和上方的状态是被计算了的，这就启发我们，横着的，竖着的，都可以归约到当前轮廓线拐角的位置来处理，所以就有了这种转移方式。
发现可以滚动数组，代码不难写出，唯一要注意的就是初始化，对第 \(0\) 行状态做处理即可。
AGC017F - Zigzagψ(｀∇´)ψ
似乎是经典题目了。
给定一个 \(N\) 层的三角形图，第 \(i\) 层有 \(i\) 个节点。
第 \(i\) 层的节点，从左到右依次标号为 \((i, 1), (i, 2), \ldots , (i, i)\)。
你需要从 \((1, 1)\) 往下画 \(M\) 条折线。
对于每条折线的每一个小段，你可以从 \((i, j)\) 画到 \((i + 1, j)\) 或者 \((i + 1, j + 1)\)。
同时你还必须保证第 \(i\) 条折线的任何一个位置必须不能处在第 \(i > 1\) 条折线的左侧，它们必须按照从左到右的顺序排列。
有 \(K\) 条限制，每条限制形如 \((A_i, B_i, C_i)\)。
表示第 \(A_i\) 条折线处于位置 \((B_i, j)\) 时，下一小段必须走向 \((B_i + 1, j + C_i)\)，也就是当 \(C_i = 0\) 时向左，当 \(C_i = 1\) 时向右。
询问不同的折线画法的方案数，对 \({10}^9 + 7\) 取模。
\(1 \le N, M \le 20\)，\(0 \le K \le M (N > 1)\)。其它变量在合理范围内。
因为折线每一步就只有两种可以走，所以显然我们可以考虑用一个二进制数来表示折线。
暴力的话是简单的，我们一个一个确定折线，计算方案数即可，这个就设 \(dp(i, msk)\) 表示考虑了前 \(i\) 条折线都满足要求且第 \(i\) 条状态为 \(msk\) 的方案数。
状态数是 \(O(m2^n)\) 的，然后转移还需要枚举上一层状态并扫一遍判断，复杂度是 \(O(nm4^n)\) 的。
然后你就发现，哈哈了，这题 \(n,m \le 20\)，复杂度上天。
注意到其实折线的转移也类似轮廓线的形式，我们依旧可以考虑按每一位依次确定每一条折线。
不妨设 \(dp(i, j, msk, k)\) 表示，考虑前 \(i\) 条折线均合法，当前考虑到了第 \(i\) 条折线的第 \(j\) 位，\(msk[1..j]\) 表示第 \(i\) 条折线的状态，\(msk[j+1..n]\) 表示上一条折线的状态且上一条状态的第 \(j\) 位在当前层的位置为 \(k\)。
这么设计是因为，第 \(i\) 条折线在第 \(j\) 层的位置可以通过 \(msk\) 算出，因为起点是知道的，但是另一条折线的前半部分被我们忽略了，所以我们还需要记录一个起点信息来进行转移。
此时如果直接做，复杂度是 \(O(mn^22^n)\) 的，还是过不了，我们考虑还有没有什么优化。
值得注意的一个点是（这应该才是这题的 key observation），第 \(i - 1\) 条折线和第 \(i\) 条折线中间有一部分是没用的，因为每次不然往下不然就要往右下，在第 \(i\) 条折线当前层位置被确定的时候，显然再往左的它都走不到了。
那么，我们把 \(i - 1\) 这条折线右边的区域和 \(i\) 这条当前有可能能去到的位置取一个交，对答案是没有影响的。
所以上一条折线的后半部分实际上可以看作是从这条折线的当前位置出发的，我们就不需要记录 \(k\) 这一维了，由于轮廓线转移是 \(O(1)\) 的，整体复杂度就是空间复杂度，我们就可以把复杂度降到 \(O(nm2^n)\)，这题开了 4s 是能跑过去的。
但是我们并不能直接沿用状态，注意到我们在做的实际上是求交，比如上图，紫色部分是我们处理过后的，可以注意到它有一个前缀的状态和原来那条线的前缀状态不对应。
显然此时一定只能是上一个折线往右走的情况，于是我们考虑处理一下即可。
然后对于题中所给限制，在转移的时候判一下就好了。
Mock20230731 T4 - dungeonψ(｀∇´)ψ
暂时咕了。