102984: [Atcoder]ABC298 E - Unfair Sugoroku
Description
Score : $500$ points
Problem Statement
Takahashi and Aoki will play a game of sugoroku.
Takahashi starts at point $A$, and Aoki starts at point $B$. They will take turns throwing dice.
Takahashi's die shows $1, 2, \ldots, P$ with equal probability, and Aoki's shows $1, 2, \ldots, Q$ with equal probability.
When a player at point $x$ throws his die and it shows $i$, he goes to point $\min(x + i, N)$.
The first player to reach point $N$ wins the game.
Find the probability that Takahashi wins if he goes first, modulo $998244353$.
How to find a probability modulo $998244353$
It can be proved that the sought probability is always rational. Additionally, the constraints of this problem guarantee that, if that probability is represented as an irreducible fraction $\frac{y}{x}$, then $x$ is indivisible by $998244353$.
Here, there is a unique integer $z$ between $0$ and $998244352$ such that $xz \equiv y \pmod {998244353}$. Report this $z$.
Constraints
- $2 \leq N \leq 100$
- $1 \leq A, B < N$
- $1 \leq P, Q \leq 10$
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$ $A$ $B$ $P$ $Q$
Output
Print the answer.
Sample Input 1
4 2 3 3 2
Sample Output 1
665496236
If Takahashi's die shows $2$ or $3$ in his first turn, he goes to point $4$ and wins.
If Takahashi's die shows $1$ in his first turn, he goes to point $3$, and Aoki will always go to point $4$ in the next turn and win.
Thus, Takahashi wins with the probability $\frac{2}{3}$.
Sample Input 2
6 4 2 1 1
Sample Output 2
1
The dice always show $1$.
Here, Takahashi goes to point $5$, Aoki goes to point $3$, and Takahashi goes to point $6$, so Takahashi always wins.
Sample Input 3
100 1 1 10 10
Sample Output 3
264077814
Input
题意翻译
两个人(分别记甲和乙)手上分别有初始值 $A$ 和 $B$。 甲有个骰子,等概率从 $1\sim P$ 中出现一个数,让甲当前值加上出现的数。乙同理,不过是等概率从 $1\sim Q$ 中出现一个数。 当前的数先大于等于 $n$ 的人胜利。甲先甩,甲乙轮流。问甲获胜的几率。答案对 $998244353$ 取模。 translated by 月Output
问题描述
Takahashi 和 Aoki 将要玩一个 sugoroku 游戏。
Takahashi 从点 $A$ 出发,Aoki 从点 $B$ 出发。他们轮流掷骰子。
Takahashi 的骰子等概率显示 $1, 2, \ldots, P$,Aoki 的骰子等概率显示 $1, 2, \ldots, Q$。
当位于点 $x$ 的玩家掷出骰子并显示 $i$ 时,他将移动到点 $\min(x + i, N)$。
第一个到达点 $N$ 的玩家赢得游戏。
如果 Takahashi 先走,求他获胜的概率,对 $998244353$ 取模。
如何求解对 $998244353$ 取模的概率
可以证明所求概率总是有理数。此外,本问题的约束条件保证,如果将该概率表示为不可约分数 $\frac{y}{x}$,则 $x$ 能被 $998244353$ 整除。
这里存在一个介于 $0$ 和 $998244352$ 之间的唯一整数 $z$,满足 $xz \equiv y \pmod {998244353}$。输出这个 $z$。
约束条件
- $2 \leq N \leq 100$
- $1 \leq A, B < N$
- $1 \leq P, Q \leq 10$
- 输入中的所有值都是整数。
输入
输入从标准输入给出,格式如下:
$N$ $A$ $B$ $P$ $Q$
输出
输出答案。
样例输入 1
4 2 3 3 2
样例输出 1
665496236
如果 Takahashi 在第一回合掷出 $2$ 或 $3$,他将移动到点 $4$ 并赢得比赛。
如果 Takahashi 在第一回合掷出 $1$,他将移动到点 $3$,而 Aoki 在下一回合将总是移动到点 $4$ 并赢得比赛。
因此,Takahashi 的获胜概率为 $\frac{2}{3}$。
样例输入 2
6 4 2 1 1
样例输出 2
1
骰子总是显示 $1$。
在这里,Takahashi 移动到点 $5$,Aoki 移动到点 $3$,Takahashi 移动到点 $6$,因此 Takahashi 总是获胜。
样例输入 3
100 1 1 10 10
样例输出 3
264077814