[ARC203C] Destruction of Walls 题解

看到 就显然分讨了。

• Case 1：

  此时显然无解。

• Case 2：

  此时答案即为从 走到 的方案数，即 。

• Case 3：

  即在 Case 2 的基础上再选一堵墙拆除。发现对于任意一条从 到 的路径，都可以选择其余任意一堵墙拆除。故答案为 。

• Case 4：

  发现此时又产生了两种情况。一种是路径长度依旧为 ，另一种是路径长度为 。

  • Case 4.1：路径长度为

    即在 Case 2 的基础上再选两堵墙拆除。尝试延续 Case 3 的做法，答案为 。可是发现此时会重复。具体地，当存在一个位置 满足 四堵墙都被拆除时，这种拆除方案会被路径 与 各计算一次。

    考虑计算被重复计算的方案数。考虑枚举 ，那么这里的答案为 。考虑从路径计数意义上化简。假设 和 是一个点，那么上式相当于在计算 到 的路径数。撤销假设，那么我们要选择路径中的一个点，将它视为 ，插入点 ，并把之后的点向右、向下各移动一个位置。可以选择的点有 个，所以上式化简为 。

  • Case 4.2：路径长度为

    此时所有墙恰好用完，所以我们只用计算长度为 的路径数量。当路径长度为 时，一定走了一次回头路，即一定向上走了一步或向左走了一步。

    若向上走了一步，那么在竖直方向上的总步数是 ，而在水平方向上的总步数依然是 。发现，如果有一步是向上的，那么它的上一步和下一步都必须是向右的。由于一定存在一步向上，所以我们可以先提前使用两个向右的行动。此时在水平方向还剩下 步。我们先假设所有竖直方向上的行动都是向下的，那么此时答案为 。接下来，我们可以从竖直方向上的第 步到第 步之间任意选择一步，并将其“反转”，即在这一步前后各加一次向右的行动，并且将这一步修改为向上。所以答案为 。

    同理，若向左走了一步，那么答案为 。

  综上所述，这一部分的答案为：

代码是好写的，所以这里就不放了。