ARC203C

casework。

容易发现

k\le n+m

，但是最短路是

n+m-2

，直接分讨：

$k<n+m-2$ ：答案是 0。
$k=n+m-2$ ：显然答案是 $\binom{n+m-2}{n-1}$ 。
$k=n+m-1$ ：显然此时再随便断掉一条边都可以。答案是 $\binom{n+m-2}{n-1}\left(n(m-1)+m(n-1)-(n+m-2)\right)$ 。
$k=n+m$ ：此时又要分讨。
- 最短路等于 $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$ 互换即可。

文章操作