题意回顾

• 给定 $W \times H$ 的网格，$K$ 个位置是洞（缺失格）。
• 使用无限个 L 形三联牌（占 3 格，形状如 L，可旋转 90° 的倍数）密铺。
• 要求：
  1. 覆盖所有非缺失格
  2. 不重叠、不出界、不覆盖缺失格
• 判断是否可行。

---

初步分析

1. 必要条件

• 非缺失格数量 $N = W \times H - K$ 必须是 3 的倍数，否则直接输出 NO。
• 当 $W = 1$ 或 $H = 1$ 时，L 形三联牌无法铺（因为 L 形至少需要 2×2 的空间才能放一个牌），但数据范围中 $W \ge 2, H \ge 2$，所以不用考虑 1 维情况。

---

核心思路

本题 $W$ 很小（最大 13），$H$ 很大（最大 $10^9$），$K$ 最多 250。
采用 按行状压DP + 矩阵快速幂 的方法。

---

2. 状态定义

我们按 列 来定义状态（因为 $W \le 13$，状态数 $2^W$ 可接受）：
设 $dp[i][mask]$ 表示处理到第 $i$ 列时，当前列的覆盖状态为 $mask$（1 表示该格已被覆盖，0 表示未覆盖）的方案是否可行。

但更常见的做法是 按轮廓线DP（插头DP）来考虑，这里我们采用 按列递推，用二进制表示当前行和下一行的覆盖需求。

---

实际上更简单且经典的做法是：

状态：$dp[i][S]$ 表示当前处理到第 $i$ 行，且该行的覆盖情况由集合 $S$ 表示（$S$ 是 $W$ 位的二进制数，1 表示该格还未被覆盖，0 表示已被覆盖）。

转移时，我们要用 L 形牌覆盖第 $i$ 行中还未覆盖的格子，并且可以延伸到第 $i+1$ 行。

---

3. 转移方法

从 $S$（当前行未覆盖集合）转移到 $T$（下一行未覆盖集合）：

我们枚举所有可能的 L 形牌放置方式，这些牌必须覆盖 $S$ 中的一些格子，并且可能覆盖第 $i+1$ 行的一些格子（这些格子在 $T$ 中为 1 表示仍未被覆盖）。

具体来说，L 形三联牌的形态有四种（旋转 90° 倍数）：

1. ##
#
2. ##
#
3. #
##
4. #
##

其中 # 表示占用的格子。

---

我们 DFS 枚举当前行 $S$ 中最左的未覆盖格，尝试用四种形态之一覆盖它，并更新 $S$ 和 $T$。

---

4. 矩阵化与快速幂

如果 $K=0$（无缺失格），那么状态转移是 齐次 的，即从 $S$ 到 $T$ 的可行性是固定的，与行号无关。

我们可以构建一个 $2^W \times 2^W$ 的布尔矩阵 $M$，其中 $M[S][T] = 1$ 表示状态 $S$ 可以转移到状态 $T$。

初始状态：$dp[0][0] = 1$（第 0 行时，所有格都未被覆盖，但第 0 行之前不存在，所以是空状态）。

最终状态：$dp[H][0] = 1$（最后一行之后，所有格都应被覆盖）。

那么问题转化为：$M^H$ 的 $(0,0)$ 项是否为 1。

---

5. 处理缺失格

当 $K > 0$ 时，矩阵 $M$ 不是完全齐次的，因为某些行有缺失格。

我们可以将 $H$ 行按缺失格所在的行号 分段，每段内没有缺失格，使用矩阵快速幂；在缺失格所在行，特殊处理转移（禁止覆盖缺失格）。

具体做法：

1. 将缺失格按 $y$ 坐标排序，将 $[1,H]$ 分成若干段 $[y_{i-1}+1, y_i]$。
2. 对每一段 $[L,R]$，长度 $len = R-L+1$，用矩阵 $M^{len}$ 转移。
3. 在缺失格所在行 $y_i$，我们修改转移矩阵：禁止覆盖缺失格对应的列。

---

6. 对小 $W$ 的特判

• $W=2$ 时，必须 $H \bmod 3 = 0$ 且 $K=0$ 才可能（实际上 $W=2$ 时 L 形三联牌无法铺满，需要具体构造验证）。
• $W=3$ 时，也有特殊模式。

---

算法步骤

1. 如果 $(W\times H - K) \bmod 3 \neq 0$，输出 NO。
2. 对缺失格按 $y$ 排序，分段处理。
3. 预处理无缺失格时的转移矩阵 $M$（通过 DFS 枚举所有可能的 L 形牌放置方式）。
4. 对每一段 $[L,R]$：
   • 用快速幂计算 $M^{len}$
   • 更新 DP 状态向量
5. 在缺失格行，特殊处理：只允许不覆盖缺失格的转移。
6. 最终检查 $dp[0]$（全 0 状态）是否可达。

---

复杂度分析

• 状态数 $N_S \le 2^W \le 8192$。
• 矩阵乘法 $O(N_S^3)$ 但 $N_S^3 \approx 5\times 10^8$，可能较慢，需要优化（用布尔矩阵+位运算）。
• 快速幂 $O(\log H)$ 次矩阵乘法。
• 总复杂度 $O(K \cdot N_S^3 \log H)$，在 $W \le 13$ 时勉强可行（需要优化）。

---

样例验证

样例 1
$W=4, H=3, K=3$
缺失格：(1,1), (1,3), (4,3)
非缺失格数 $12-3=9$，是 3 的倍数。
可以构造铺法，输出 YES。

样例 2
$W=5, H=2, K=4$
非缺失格 $10-4=6$，是 3 的倍数，但实际无法铺，输出 NO。

样例 3
$W=2, H=3, K=0$
非缺失格 6，是 3 的倍数，可以铺，输出 YES。

---

总结

本题是 状压DP + 矩阵快速幂 的经典题，难点在于：

1. 状态定义与 L 形牌覆盖的转移枚举
2. 大 $H$ 时用矩阵快速幂加速
3. 缺失格的分段处理

通过合理的状态设计和矩阵优化，可以在规定时间内解决问题。