ATABC298E Unfair Sugoroku
（笑）
题意
有一个长为 \(N\) 行的棋盘，两枚棋子初始时分别位于 \(A\)，\(B\) 两个位置，分别记为 \(a\) 与 \(b\)。两枚棋子分别对应两枚骰子，分别可以等概率的投掷出 \(1 \sim P\) 与 \(1 \sim Q\) 的点数，并将其对应的棋子移动到 \(\min(N, i + X)\) 的位置上，其中 \(i\) 是这枚棋子当前的位置，\(X\) 是掷出的点数。率先到达 \(N\) 的棋子获胜。
现在轮流移动这两枚棋子（\(a\) 先动），问 \(PA \bmod 998244353\) 的值是多少，其中 \(PA\) 是 \(a\) 获胜的概率。
\(N \le 100\)，\(A, B \le N\)，\(P, Q \le 10\)。
思路
我们先不考虑计算，直接写个搜索的框架来模拟游戏过程吧。
void dfs(int dep = 1, int apos = a, int bpos = b) {
if (dep & 1) {
for (int i = 1; i <= p; i++) {
if (apos + i >= n) {
...
} else {
dfs(dep + 1, apos + i, bpos);
}
}
} else {
for (int i = 1; i <= q; i++) {
if (bpos + i >= n) {
...
} else {
dfs(dep + 1, apos, bpos + i);
}
}
}
return;
}
根据题意，这个搜索是很好写的。然后我们再来考虑计算。
题目中说对于搜索树中的每一个决策，也就是骰子掷出的点数，是等概率的，那么对于 \(a\)，投出每一个点数的概率就是 \(\dfrac{1}{P}\)，对于 \(b\) 是同理的，为 \(\dfrac{1}{Q}\)。那么对于状态三元组 \((dep, cura, curb)\)，其中 \(dep\) 表示搜索树深度，\(cura\) 表示 \(a\) 当前位置，\(curb\) 表示 \(b\) 当前位置，我们很容易就可以写出一个式子：
\[P(dep, cura, curb) = \begin{cases} 1 & cura \ge N \\ 0 & curb \ge N \\ \sum_{i = 1}^{P}{\frac{P(dep + 1, cura + i, curb)}{P}} & dep \bmod2 = 1 \\ \sum_{i = 1}^{Q}{\frac{P(dep + 1, cura, curb + i)}{Q}} & dep \bmod 2 = 0 \end{cases} \]其中 \(P(dep, cura, curb)\) 记为当前状态获胜的概率。
那么我们就可以在上边那个搜索框架的基础上，添加计算的部分。
i64 dfs(int dep = 1, int apos = a, int bpos = b) {
static const i64 MOD = 998244353;
static const i64 invp = inv(p, MOD), invq = inv(q, MOD);
i64 res = 0;
if (dep & 1) {
for (int i = 1; i <= p; i++) {
if (apos + i >= n) {
(res += invp) %= MOD;
} else {
(res += invp * dfs(dep + 1, apos + i, bpos) % MOD) %= MOD;
}
}
} else {
for (int i = 1; i <= q; i++) {
if (bpos + i >= n) {
continue;
} else {
(res += invq * dfs(dep + 1, apos, bpos + i) % MOD) %= MOD;
}
}
}
return res;
}
这样就做完了吗？当然没有，单纯地像这样爆搜的话，时间复杂度明显是指数级的，我们需要优化搜索的部分。
我们发现，上述搜索过程显然是满足无后效性的，因此我们可以通过记忆化来优化时间复杂度。
于是就有了下边的代码：
i64 dfs(int dep = 1, int apos = a, int bpos = b) {
static const i64 MOD = 998244353;
static const i64 invp = inv(p, MOD), invq = inv(q, MOD);
if (f[apos][bpos] != -1) {
return f[apos][bpos];
}
i64 res = 0;
... // 省略搜索过程
f[apos][bpos] = res;
return res;
}
然后兴致冲冲地测第三个样例，发现错了。
难道是不能记忆化？当然不是，问题出在没有考虑好状态。我们发现，对于一个状态 \((cura, curb)\) ，其实是存在两种可能的，一种是当前为 \(a\) 的回合，另一种是当前为 \(b\) 的回合，所以记忆化数组还要多加一维，用于表示当前是谁先手，才可以避免状态混乱。
i64 dfs(int dep = 1, int apos = a, int bpos = b) {
static const i64 MOD = 998244353;
static const i64 invp = inv(p, MOD), invq = inv(q, MOD);
if (f[apos][bpos][dep & 1] != -1) {
return f[apos][bpos][dep & 1];
}
i64 res = 0;
... // 省略搜索过程
f[apos][bpos][dep & 1] = res;
return res;
}
代码
#include <bits/stdc++.h>
using i64 = long long;
using d80 = long double;
int n, a, b, p, q;
i64 all;
std::vector<std::vector<std::vector<i64>>> f;
i64 exgcd(i64 a, i64 b, i64 &x, i64 &y) {
if (!b) {
x = 1, y = 0;
return a;
}
i64 d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
i64 inv(i64 num, i64 mod) {
i64 x, y;
exgcd(num, mod, x, y);
return (x % mod + mod) % mod;
}
i64 dfs(int dep = 1, int apos = a, int bpos = b) {
static const i64 MOD = 998244353;
static const i64 invp = inv(p, MOD), invq = inv(q, MOD);
if (f[apos][bpos][dep & 1] != -1) {
return f[apos][bpos][dep & 1];
}
i64 res = 0;
if (dep & 1) {
for (int i = 1; i <= p; i++) {
if (apos + i >= n) {
(res += invp) %= MOD;
} else {
(res += invp * dfs(dep + 1, apos + i, bpos) % MOD) %= MOD;
}
}
} else {
for (int i = 1; i <= q; i++) {
if (bpos + i >= n) {
continue;
} else {
(res += invq * dfs(dep + 1, apos, bpos + i) % MOD) %= MOD;
}
}
}
f[apos][bpos][dep & 1] = res;
return res;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cin >> n >> a >> b >> p >> q;
f.resize(n + 50, std::vector<std::vector<i64>>(n + 50, std::vector<i64>(2, -1)));
std::cout << dfs() << "\n";
return 0;
}