CROI-R3 比赛总结
T1
T2
T3
题意
给你一个 \(2 \times n\) 的网格，需要填充以下五种砖块：
- \(1 \times 1\) 的小砖块
- 四种旋转的 L 型砖块（每种覆盖 \(3\) 个格子）
有 \(m\) 个格子已经被预先填充，不能再用砖块覆盖。要求计算填充剩余格子的方案数。结果对 \(10^9+7\) 取模。
考点
状压 DP、矩阵快速幂
简析
由于砖块最多跨越两列，我们可以按列处理，只需要关注当前列和下一列的情况。而且，填充第 \(i\) 列时，只需要知道第 \(i-1\) 列的填充状态和第 \(i\) 列的预先填充情况
不妨定义 \(dp_{i, st}\) 表示处理到第 \(i\) 列，且第 \(i\) 列的填充状态为 \(st\) 时的方案数。其中 \(st\) 是 \(2\) 位二进制数，第 0 位表示第一行是否已被填充，第 1 位表示第二行是否已被填充。
对于每一列，我们需要考虑：
-
该列哪些格子已被预先填充；
-
从前一列继承的未完成填充会对状态转移有什么影响（由状态 \(st\) 表示）；
-
方案数怎么转移。
不妨设 \(b_0\) 表示第 \(i\) 列第一行是否被预先填充，\(b_1\) 表示第 \(i\) 列第二行是否被预先填充。
我们知道，如果某个位置已被预先填充，那么它不能再用砖块覆盖，且在状态 \(st\) 中，该位置必须标记为已填充。
因此，对于当前列 \(i\)，其从上一列继承的状态 \(st\) 表示哪些位置是 L 型砖块延伸到这一列的部分。这就说明，我们需要填充的是既没有被预先填充，也没有被继承状态覆盖的位置。
然后分类讨论四种状态的转移情况即可。过于繁杂，不予演示。
这种做法对于 \(n \le 10^5\) 是可行的，但对于 \(n \le 10^{18}\) 完全不可行。
接着我们注意到，在没有预先填充格子的连续区间内，状态转移是齐次的。这意味着：如果连续 \(k\) 列都没有预先填充的格子，那么它们的转移矩阵是相同的。
先设状态向量。容易知道，对于没有预先填充的列，存在一个 4×4 的转移矩阵。
对于一般情况，转移矩阵取决于：当前列的预先填充情况、下一列的预先填充情况、是否是最后一列。
可以定义一个函数 get_T(b0, b1, nb0, nb1, last)：
b0, b1：当前列第一行、第二行是否已预先填充nb0, nb1：下一列第一行、第二行是否已预先填充last：当前列是否是最后一列
这个函数返回一个 4×4 矩阵，其中 mt[st1][st2] 表示从状态 st2 转移到状态 st1 的方案数。
对于没有任何预先填充的列，其无填充状态的转移矩阵 mt 为：
| 从 / 到 | 00 | 01 | 10 | 11 |
|---|---|---|---|---|
| 00 | 1 | 0 | 0 | 1 |
| 01 | 1 | 0 | 0 | 0 |
| 10 | 1 | 0 | 0 | 0 |
| 11 | 1 | 1 | 1 | 2 |
解释：
- 从任何状态都可以转移到 00：用两个 1×1 填充当前列
- 从状态 00 可以转移到 11：用 L 型砖块有两种方式
- 从状态 00 可以转移到 01：用覆盖当前列和下一列的 L 型
- 从状态 00 可以转移到 10：用另一种覆盖当前列和下一列的 L 型
所以我们需要分段处理，在处理关键列时，使用特殊的转移矩阵，在处理连续的无填充列时，使用矩阵快速幂加速。