[ARC203C] Destruction of Walls 题解
ToBeDetermined · · 题解
Upd on 8.11：将
看到
-
Case 1：
K \lt H + W - 2 此时显然无解。
-
Case 2：
K = H + W - 2 此时答案即为从
(1, 1) 走到(H, W) 的方案数，即\binom{H + W - 2}{H - 1} 。 -
Case 3：
K = H + W - 1 即在 Case 2 的基础上再选一堵墙拆除。发现对于任意一条从
(1, 1) 到(H, W) 的路径，都可以选择其余任意一堵墙拆除。故答案为\binom{H + W - 2}{H - 1} \cdot \binom{2(H - 1)(W - 1)}{1} 。 -
Case 4：
K = H + W 发现此时又产生了两种情况。一种是路径长度依旧为
H + W - 2 ，另一种是路径长度为H + W 。- Case 4.1：路径长度为
H + W - 2
即在 Case 2 的基础上再选两堵墙拆除。尝试延续 Case 3 的做法，答案为
\binom{H + W - 2}{H - 1} \cdot \binom{2(H - 1)(W - 1)}{2} 。可是发现此时会重复。具体地，当存在一个位置(x, y) 满足(x, y) \to (x + 1, y), (x, y) \to (x, y + 1), (x + 1, y) \to (x + 1, y + 1), (x, y + 1) \to (x + 1, y + 1) 四堵墙都被拆除时，这种拆除方案会被路径\dots \to (x, y) \to (x + 1, y) \to (x + 1, y + 1) \to \dots 与\dots \to (x, y) \to (x, y + 1) \to (x + 1, y + 1) \to \dots 各计算一次。考虑计算被重复计算的方案数。考虑枚举
(x, y) ，那么这里的答案为\sum_{x = 1}^{H - 1} \sum_{y = 1}^{W - 1} \binom{x + y - 2}{x - 1} \cdot \binom{H + W - x - y - 2}{H - x - 1} 。考虑从路径计数意义上化简。假设(x, y) 和(x + 1, y + 1) 是一个点，那么上式相当于在计算(1, 1) 到(H - 1, W - 1) 的路径数。撤销假设，那么我们要选择路径中的一个点，将它视为(x, y) ，插入点(x + 1, y + 1) ，并把之后的点向右、向下各移动一个位置。可以选择的点有(H + W - 3) 个，所以上式化简为\binom{H + W - 4}{H - 2} \cdot (H + W - 3) 。- Case 4.2：路径长度为
H + W
此时所有墙恰好用完，所以我们只用计算长度为
H + W 的路径数量。当路径长度为H + W 时，一定走了一次回头路，即一定向上走了一步或向左走了一步。若向上走了一步，那么在竖直方向上的总步数是
H + 1 ，而在水平方向上的总步数依然是W - 1 。发现，如果有一步是向上的，那么它的上一步和下一步都必须是向右的。由于一定存在一步向上，所以我们可以先提前使用两个向右的行动。此时在水平方向还剩下W - 3 步。我们先假设所有竖直方向上的行动都是向下的，那么此时答案为\binom{H + W - 2}{H + 1} 。接下来，我们可以从竖直方向上的第2 步到第H 步之间任意选择一步，并将其“反转”，即在这一步前后各加一次向右的行动，并且将这一步修改为向上。所以答案为\binom{H + W - 2}{H + 1} \cdot (H - 1) 。同理，若向左走了一步，那么答案为
\binom{H + W - 2}{W + 1} \cdot (W - 1) 。综上所述，这一部分的答案为：
- Case 4.1：路径长度为
代码是好写的，所以这里就不放了。