1 条题解

  • 0
    @ 2023-10-17 16:04:29

    芙莉莲的第二次迷宫之旅

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

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

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

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

    先讲讲 H H 题不旋转坐标轴的解法,还是一个尽量分开看 x x y y 的思路。每个维度上都是 1,1,0 1, -1, 0 的排列,一共 r r 个数,最后和为输入给定的 x0 x_0 y0 y_0 。可以发现当 Δx \Delta x 不为 0 0 时, Δy \Delta y 必为 0 0 ,反之亦然。固枚举 0 0 的个数 r0 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 \ 轴的正半轴 + 第一象限 (+原点) 。将之定义为 第一部分 。类似的,定义 x 轴的负半轴+第二象限 x \ 轴的负半轴 + 第二象限 第二部分 ,第三象限为 第三部分y 轴负半轴+第四象限 y \ 轴负半轴 + 第四象限 第四部分。那么我们要求的就是只经过 第一部分 的方案数。

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

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

    • 1

    信息

    ID
    197
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    (无)
    递交数
    127
    已通过
    12
    上传者