Subtask #1：$n, m \le 1000 \ (30 \ pts)$

直接递推。令 $f[i][j]$ 表示从起点走到 $(i,j)$ 的方案数。使用 $f[i][j]=f[i-1][j]+f[i][j-1]$ 递推即可。注意本题求的是 $233^{f[n-1][m-1]}$ 的值，所以我们需要计算的是 $f[n-1][m-1] \bmod 999911658$ 的值，而不是 $f[n-1][m-1] \bmod 999911659$ 的值。时间复杂度 $\Theta(nm)$。提交记录：http://zhengruioi.com/submission/31143

Subtask #2：$n=m,k=0 \ (20 \ pts)$

观察到这种网格如果没有额外危险点，从 $(0,0)$ 走到 $(n-1,n-1)$ 的方案数为卡特兰数的第 $n-1$ 项。而我们要计算的是答案 $\bmod 999911658 = 2 \times 3 \times 4679 \times 35617$ 的结果，所以只需对每个素因子分别使用 $\text {Lucas}$ 计算组合数，然后将答案使用中国剩余定理合并即可。结合暴力可得 $50 \ pts$。

Subtask #3：$k=0 \ (20 \ pts)$

这个数据点要求我们理解卡特兰数的本质。当然如果你在 $\text C$ 班好好听讲也可以作出这个点。我们考虑从 $(x_0, y_0)$ 走到 $(x_1, y_1)$ 的方案数。我们考虑先计算出没有 $x>y$ 不能走的限制的方案数，再减去不合法的方案数。总方案数显然是：

$$\binom{x_1-x_0+y_1-y_0}{x_1-x_0}$$

对于不合法的方案，我们考虑这个路径。它一定穿过一条 $x = y$ 的直线。也就是说，他一定与这条直线有交点。

*-*-*-*-*-*-*
 \| | | | | |
* *-*-*-*-*-*
   \| | | | |
* * *-*-*-*-*
     \| | | |
* * * *-*-*-*
       \| | |
* * * * *-*-*

我们考虑将这条路径和这条直线的第一个交点取出，然后将这条路径中这个交点之前的路径全部以这条直线为对称轴翻转过来。这样，每条路径就队对应了从一个新的起点（原起点以直线为对称轴后翻转得到的点）和原终点的所有路径条数。这样的路径条数为：

$$\binom{x_1-x_0+y_1-y_0}{y_1-y_0+(y_0-x_0+1)}$$

于是我们就可以用刚才 $\text {Subtask #2}$ 中介绍的的技巧算出这个值了。结合前述算法可得 $70 \ pts$。提交记录：http://zhengruioi.com/submission/31162

Subtask #3 的另类做法

由于数据随机，并且最大模数只有 $35617$，所以组合数到一定范围 $\bmod 35617$ 就等于 $0$ 了。于是我们只需要输出 $233^0=1$ 即可获得 $40 \ pts$。这个故事告诉我们：

• 人是要有信仰的
• 出题人生成数据是不应该纯随机，否则会出事

Subtask #4 $(n,m \le 10^9, k \le 1000)$

我们考虑容斥。先令从 $(x_0, y_0)$ 走到 $(x_1, y_1)$ 的方案数为 $paths(x_0, y_0, x_1, y_1)$。令 $f[i]$ 表示到达第 $i$ 个危险点，并且不到达其他的危险点的总方案数。转移方程：$f[i]=paths(0,0,x_i,y_i)-\sum_{x_j\le x_i, y_j\le y_i}paths(x_j, y_j, x_i, y_i)$。于是，我们就可以在 $\Theta(k^2)$ 的时间内解决这个问题了。提交记录：http://zhengruioi.com/submission/31256

总结

这个题是一道数论五合一，完美的覆盖了 $\text {C}$ 班上课的知识点，是一道综合性的好题。希望这道题能为您的正睿 $\text {OI}$ 暑假学习之旅画上 $\text {van}$ 美的句号。