如题，感谢 @MatrixGroup 老师的指导。

实际上是要你求出网格图上从 (0,0)(0, 0) 走到 (n,n)(n, n)，每次只能向右或者向上走，恰好走到直线 x=yx = y 上 kk 次（不包括首尾，所以 k∈[0,n−1]k \in [0, n - 1]），并且始终满足 x≥yx \ge y 的路径条数。

你就说这个东西是不是 kk 个卡特兰数状物卷起来嘛。

  • 多项式快速幂即可。

其实没必要，这个东西应该是可以直接 GF 推的，但是有聪明的双射。

考虑转化成从 (1,0)(1, 0) 走到 (n,n−1)(n, n - 1) 并恰好走到直线 x=yx = y 上 kk 次的方案数。然后你发现每次走到 x=yx = y 的操作都是 UR，我们将每一个这样的操作都替换成 R，这样我们就得到了一个到“从 (1,0)(1, 0) 走到 (n,n−k−1)(n, n - k - 1) 且不碰直线 x=yx = y 的路径”的映射。

考虑映射回去。那么我们考虑倒着操作，从 (n,n−1)(n, n - 1) 按照该路径的方案往回走，如果碰到对角线就往下走一步，这样就生成了唯一一条原本的路径。不难发现如果该路径没有碰到直线 x=yx = y，那么原本的路径一定不会走到该路径下面，否则原本的路径会在往回走的时候遇到的第一个（也就是本来的最后一个）碰到 x=yx = y 的地方走到该路径下面，这个映射是不合法的。

那么我们成功地构建了双射，所以翻折容斥即可得到原问题答案为：

(2n−k−2n−1)−(2n−k−2n)\binom{2n - k - 2}{n - 1} - \binom{2n - k - 2}n

显然上述过程是完全可以拓展到终点为 (n,m)(n, m)（n≥mn \ge m）的情况的，类似地，答案为：

(n+m−k−2n−1)−(n+m−k−2n)\binom{n + m - k - 2}{n - 1} - \binom{n + m - k - 2}n

应用（其实是为了做这个题才来研究这个东西的）：ARC186D Polish Mania。