芙莉莲的第二次迷宫之旅

首先这题出题人被 ast123 的解法 完爆了（

这题和 H 很像，只是多了个要在第一象限内的限制。

先聊聊为什么会想到这样改。在 $H$ 的解法中，有一步是计算 $1$ 和 $-1$ 的排列方案数，这让我想到了 洛谷 P1754 球迷购票问题 （虽然最早是在一本书上看到的，但我忘了是红书还是蓝书了）。所以就加了个只能在第一象限内的限制。

再看看改完后的解法。在 $H$ 中，通过旋转坐标轴来使得 $x$ 维的坐标改变与 $y$ 维的坐标改变分离，在本题如果直接照搬，会发现要保证在第一象限内移动的话，限制条件就变成了 $|x| \le y$ （顺时针旋转的时候），反而没法将 $x$ 维与 $y$ 维分离。最后还是选择了改变 $H$ 题的旋转前做法，就套一层上面那题的 $dp$ （所以反而感觉这题给改无聊了）。

先讲讲 $H$ 题不旋转坐标轴的解法，还是一个尽量分开看 $x$ 与 $y$ 的思路。每个维度上都是 $1, -1, 0$ 的排列，一共 $r$ 个数，最后和为输入给定的 $x_0$ 或 $y_0$ 。可以发现当 $\Delta x$ 不为 $0$ 时， $\Delta y$ 必为 $0$，反之亦然。固枚举 $0$ 的个数 $r_0$ 然后分别计算两个维度的方案数相乘再乘上组合数即可。计算方法即为球迷购票问题的解法。

#include <cstdio>
#include <iostream>

using namespace std;
const int N = 2005, Mod = 998244353;

int T;
int f[N][N]; // f[r][x] 表示在第一象限内，用 r 步在某个维度走到 x 的方案数
int C[N][N];

int Add(int x, int y) {
    int tmp = x + y;
    return tmp >= Mod ? tmp - Mod : tmp;
}

int main() {
    f[0][0] = 1;
    for (int r = 1; r <= 2000; ++r) {
        f[r][0] = f[r - 1][1];
        for (int x = 1; x <= r; ++x)
            f[r][x] = Add(f[r - 1][x + 1], f[r - 1][x - 1]);
    }
    C[0][0] = 1;
    for (int i = 1; i <= 2000; ++i) {
        C[i][0] = 1;
        for (int j = 1; j <= i; ++j)
            C[i][j] = Add(C[i - 1][j], C[i - 1][j - 1]);
    }

    scanf("%d", &T);
    while (T--) {
        // cerr << T << endl;
        int x, y, r;
        scanf("%d%d%d", &x, &y, &r);
        if (x > r || y > r || x + y > r) {
            cout << 0 << endl;
            continue;
        }
        int Ans = 0;
        for (int i = 0; i <= r; ++i) { // 由于实际的移动是 (1, 0) (-1, 0) (0, 1) (0, -1) 所以 x 与 y 的 0 要错开来
            // f[i][x] 与 f[r - i][y] 还有 C(r, i) ，因为 f 里只有 1 和 -1 的顺序
            Ans = Add(Ans, 1ll * f[i][x] * f[r - i][y] % Mod * C[r][i] % Mod);
        }
        printf("%d\n", Ans);
    }
    return 0;
}

如果这么看的话，这题反而被改的中规中矩了。所以感谢 @ast123 给这题带来了更优的解法。

首先题目里对象限的定义并不严谨 （我有罪） ，实际上是 $x \ 轴的正半轴 + y \ 轴的正半轴 + 第一象限 （+原点）$ 。将之定义为 第一部分 。类似的，定义 $x \ 轴的负半轴 + 第二象限$ 为 第二部分 ，第三象限为 第三部分 ，$y \ 轴负半轴 + 第四象限$ 为 第四部分。那么我们要求的就是只经过 第一部分 的方案数。

那么在已有 $H$ 题解法的前提下，考虑容斥。定义 $f(x, y)$ 表示从 $(x, y)$ 到题目给定的 $(x_0, y_0)$ 的方案数（不受限制的方案数）。那么实际上，从 $(0, 0)$ 出发，必须经过 第二部分 的方案数与 $f(-2, 0)$ 相等（因为 $x$ 维上必然有一个 $-1$ 和一个 $1$）。同样的，必须经过 第四部分 的方案数与 $f(0, -2)$ 相等，而必须同时经过 第二部分 与 第四部分 的方案数即为 $f(-2, -2)$ 。所以最终结果即为 $f(0, 0) - f(-2, 0) - f(0, -2) + f(-2, -2)$ ，也就是做四遍 $H$ ，所以数据范围其实可以开到与 $H$ 相同（对不起我太菜了）。

可能有人会疑惑 第三部分 呢？实际上，在经过上面的定义后，想要经过 第三部分 ，就一定会经过 第二部分 或 第四部分 ，即为 $第三部分_{只经过第二部分}$ ， $第三部分_{只经过第四部分}$ 以及 $第三部分_{同时经过第二第四部分}$ ，这个容斥在上面其实已经完成了。