確率DP. ゲームの終端から決めていく.
実装1
再帰で奥の方から決めていく. 決まった場所は答えをメモしておくことで,同じ計算を省略できる. 再帰なら,仮にゲームの遷移が複雑な場合でも可能.
実装2
for でも実装できる.今居る座標を\(x\)とおけば,\(x\)における答えを求めるときに \(x\)より大きい座標しか参照しないため. この場合,大きい座標から for を回すことに注意.
高橋君と青木君の座標をそれぞれ \(x,y\) とおく. もう一つの注意は,\(x < n-1, y < n-1\) の範囲をループするのであって, \(x = n-1\) または \(y = n-1\) の場合は個別に求めておく.
使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
mint dp[115][115][2];
bool vis[115][115][2];
int main() {
ll n; cin >> n;
vll a(2), p(2);
cinv(a); rep(i,2) a[i]--;
cinv(p);
// 局面 (x,t) のとき,先手が勝つ確率
auto f = [&](auto f, vll x, ll t) -> mint {
if(x[0] >= n-1) return mint(1);
if(x[1] >= n-1) return mint(0); // rem
if(vis[x[0]][x[1]][t]){
return dp[x[0]][x[1]][t];
}
mint ret = 0;
rep1(i,p[t]){
vll y(2);
y[t] = x[t] + i;
y[t^1] = x[t^1];
ret += f(f, y, t^1);
}
ret /= mint(p[t]);
vis[x[0]][x[1]][t] = true;
return dp[x[0]][x[1]][t] = ret;
};
cout << f(f, a, 0).val() << endl;
return 0;
}