Official

E - Unfair Sugoroku Editorial by cn449


\(dp_{i,j,f}\) を高橋君が地点 \(i\)、青木君が地点 \(j\) にいて、\(f=0\) ならば次の手番が高橋君、\(f = 1\) ならば次の手番が青木君としたときの高橋君の勝率とします。求める値は \(dp_{A,B,0}\) です。
具体的に dp の遷移を考えていきます。
まずは、\(dp_{i,j,0}\) の値について考えます。高橋君は \(k = 1,2, \ldots, P\) に対し地点 \(\min(i+k,N)\) に等確率で進むので、\(dp_{i,j,0} = \frac{1}{P}\displaystyle\sum_{k=1}^{P}dp_{\min(i+k,N),j,1}\) が成り立ちます。
同様に \(dp_{i,j,1}\) の値を考えると、青木君は \(k = 1,2, \ldots, Q\) に対し地点 \(\min(j+k,N)\) に等確率で進むので、\(dp_{i,j,1} = \frac{1}{Q}\displaystyle\sum_{k=1}^{Q}dp_{i,\min(j+k,N),0}\) が成り立ちます。
上の dp 配列についての関係式より、\(i\) および \(j\) の降順に計算していくと dp 配列の値が求まることがわかります。
\(i < N\) に対し \(dp_{N,i,f} = 1, dp_{i,N,f} = 0\) であることを用いると、答えを求めることができました。
\(\text{mod } 998244353\) における \(P\)\(Q\) の逆元を \(\mathrm{O}(P+Q)\) 時間で求めることにより、時間計算量は \(\mathrm{O}(N^2(P+Q))\) となります(ユークリッドの互除法などにより \(\log 998244353\) 程度の時間計算量をかけても問題なく間に合います)。
また、累積和を用いることで時間計算量 \(\mathrm{O}(N^2)\) とすることもできます。

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: