1 条题解
-
0
芙莉莲的第二次迷宫之旅
首先这题出题人被 ast123 的解法 完爆了(这题和 H 很像,只是多了个要在第一象限内的限制。
先聊聊为什么会想到这样改。在 的解法中,有一步是计算 和 的排列方案数,这让我想到了 洛谷 P1754 球迷购票问题 (虽然最早是在一本书上看到的,但我忘了是红书还是蓝书了)。所以就加了个只能在第一象限内的限制。
再看看改完后的解法。在 中,通过旋转坐标轴来使得 维的坐标改变与 维的坐标改变分离,在本题如果直接照搬,会发现要保证在第一象限内移动的话,限制条件就变成了 (顺时针旋转的时候),反而没法将 维与 维分离。最后还是选择了改变 题的旋转前做法,就套一层上面那题的 (所以反而感觉这题给改无聊了)。
先讲讲 题不旋转坐标轴的解法,还是一个尽量分开看 与 的思路。每个维度上都是 的排列,一共 个数,最后和为输入给定的 或 。可以发现当 不为 时, 必为 ,反之亦然。固枚举 的个数 然后分别计算两个维度的方案数相乘再乘上组合数即可。计算方法即为球迷购票问题的解法。
#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 给这题带来了更优的解法。
首先题目里对象限的定义并不严谨
(我有罪),实际上是 。将之定义为 第一部分 。类似的,定义 为 第二部分 ,第三象限为 第三部分 , 为 第四部分。那么我们要求的就是只经过 第一部分 的方案数。那么在已有 题解法的前提下,考虑容斥。定义 表示从 到题目给定的 的方案数(不受限制的方案数)。那么实际上,从 出发,必须经过 第二部分 的方案数与 相等(因为 维上必然有一个 和一个 )。同样的,必须经过 第四部分 的方案数与 相等,而必须同时经过 第二部分 与 第四部分 的方案数即为 。所以最终结果即为 ,也就是做四遍 ,所以数据范围其实可以开到与 相同(对不起我太菜了)。
可能有人会疑惑 第三部分 呢?实际上,在经过上面的定义后,想要经过 第三部分 ,就一定会经过 第二部分 或 第四部分 ,即为 , 以及 ,这个容斥在上面其实已经完成了。
- 1
信息
- ID
- 197
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- (无)
- 递交数
- 127
- 已通过
- 12
- 上传者