E - Unfair Sugoroku
当前没有测试数据。
E - Unfair Sugoroku
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:
Output
Print the answer.
4 2 3 3 2
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}$.
6 4 2 1 1
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.
100 1 1 10 10
264077814