E - Unfair Sugoroku Editorial by en_translator
Let \(dp_{i,j,f}\) be the probability that Takahashi wins when Takahashi and Aoki is at points \(i\) and \(j\), respectively, where \(f=0\) if the next turn is Takahashi’s and \(f=1\) if Aoki’s. The sought value is \(dp_{A,B,0}\).
We consider the transitions of the DP (Dynamic Programming).
We first consider the value \(dp_{i,j,0}\). For \(k = 1,2, \ldots, P\), Takahashi advances to point \(\min(i+k,N)\) with equal probability, so \(dp_{i,j,0} = \frac{1}{P}\displaystyle\sum_{k=1}^{P}dp_{\min(i+k,N),j,1}\).
Similarly, we consider \(dp_{i,j,1}\). For \(k = 1,2, \ldots, Q\), Aoki advances to point \(\min(j+k,N)\) with equal probability, so \(dp_{i,j,1} = \frac{1}{Q}\displaystyle\sum_{k=1}^{Q}dp_{i,\min(j+k,N),0}\).
By the relations of the DP array above, we can evaluate the DP array in descending order of \(i\) and \(j\).
Using \(dp_{N,i,f} = 1\) and \(dp_{i,N,f} = 0\) for \(i < N\), we could find the answer.
Evaluating the inverse of \(P\) and \(Q\) in \(\text{mod } 998244353\) in an \(\mathrm{O}(P+Q)\) time, the complexity is \(\mathrm{O}(N^2(P+Q))\) time. (One can use Euclidean algorithm spending about \(\log 998244353\) time, still within the time limit.)
One can also utilize cumulative sums to reduce the time complexity to \(\mathrm{O}(N^2)\).
Sample code using ACL
#include <iostream>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using mint = static_modint<998244353>;
mint dp[110][110][2];
int main() {
int n, a, b, p, q;
cin >> n >> a >> b >> p >> q;
for (int i = 0; i < n; i++) for (int f = 0; f < 2; f++) {
dp[n][i][f] = 1;
dp[i][n][f] = 0;
}
for (int i = n - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
for (int k = 1; k <= p; k++) {
dp[i][j][0] += dp[min(n, i + k)][j][1];
}
dp[i][j][0] /= p;
for (int k = 1; k <= q; k++) {
dp[i][j][1] += dp[i][min(n, j + k)][0];
}
dp[i][j][1] /= q;
}
}
cout << dp[a][b][0].val() << '\n';
}
posted:
last update: