ARC203C

_jimmywang_ · 2025-08-03 22:51:23 · 个人记录

casework。

容易发现 k\le n+m，但是最短路是 n+m-2，直接分讨：

• - 最短路等于 $n+m-2$，这意味着这是在选择一条最短路的基础上，接着断两条边形成的。但是 $(x,y)\to(x,y+1)\to(x+1,y)$ 和 $(x,y)\to(x+1,y)\to(x+1,y)$ 这两条路径会互相把对方算一次，算重了，要减掉。这个减掉的值是在算“选定一个田字格，经过其左上角和右下角的方案数”。代数或组合推导可得 $(n+m-3)\binom{n+m-4}{n-2}$。 - 最短路等于 $n+m$，这意味着我们要恰好向上或向左走一次。以向上为例，那么其前后两步一定是向右，我们把这个“右上右”的组合叫做 $S$。那么此时相当于我们要向下走 $n+1$ 次，向右走 $m-3$ 次，然后把向下的 $n+1$ 次中的某一次（不能是第一次，不然向上超界了；也不能是最后一次，不然前 $n$ 次向下已经导致向下超界）替换为 $S$。这样组合起来恰好走了 $n-1$ 次下和 $m-1$ 次右。因此答案是 $(n-1)\binom{n+m-2}{m-3}$。向左的情况 $n,m$ 互换即可。