No.1547 [Cherry 2nd Tune *] Probability of a Chance Victory
Apology
During the contest, it was found that test cases violating the constraints existed until around 22:33 on 2021/06/11. After correcting them to test cases that satisfy the constraints and rejudging, we found that 5 participants had received incorrect verdicts caused by the constraint violation, when their submissions should have been judged correct. We apologize to those affected.Problem Statement
Two players, A and B, play the following game. Here, A and B each have a coin that lands heads with probability $\frac{M_A}{N_A}, \frac{M_B}{N_B}$, respectively.
The game is played with these coins as follows.
- Assign $0$ to the variables $X,Y$.
- A tosses their coin.
- Depending on the result of the toss, do the following.
- If it is heads, add $1$ to $X$. Then, if $X=S$, the game ends immediately, with A winning and B losing. If $X < S$, return to 2.
- If it is tails, proceed to 4.
- B tosses their coin.
- Depending on the result of the toss, do the following.
- If it is heads, subtract $1$ from $X$. Then, if $X=-T$, the game ends immediately, with B winning and A losing. If $X > -T$, return to 4.
- If it is tails, proceed to 6.
- Add $1$ to $Y$. Then, if $Y < K$, return to 2. If $Y=K$, the game ends and both A and B lose.
Note that when the coin held by A or B is tossed, exactly one of heads or tails comes up.
Let $\alpha, \beta$ be the probabilities that A and B win this game, respectively. Find $\alpha \pmod{998244353}, \beta \pmod{998244353}$.
It can be proved that, under the constraints of this problem, both $\alpha, \beta$ are rational numbers.
▶What is (rational number)$\pmod{998244353}$?
Under the constraints of this problem, it is guaranteed that the rational number $H$ to be output can be expressed as $H=\frac{P}{Q}$ using an integer $P$ and an integer $Q$ that is not a multiple of $998244353$. In this case, there exists a unique integer $X$ between $0$ and less than $998244353$ satisfying $P \equiv QX~\pmod{998244353}$, and using this integer $X$, we define $H \pmod{998244353}=X$.
Constraints
- $0 \leq M_A \leq N_A < 998244353$
- $0 \leq M_B \leq N_B < 998244353$
- $N_A, N_B \neq 0$
- $1 \leq S,T \leq 50$
- $1 \leq K \leq 10^9$
- All inputs are integers.
Input
$M_A$ $N_A$ $S$ $M_B$ $N_B$ $T$ $K$
Output
The output consists of $2$ lines. Let $\alpha, \beta$ be the probabilities that A and B win, respectively. Print $\alpha \pmod{998244353}$ on line $1$ and $\beta \pmod{998244353}$ on line $2$. Do not forget the newline.
Sample
Sample 1
Input
1 2 1 1 2 2 1
Output
499122177 873463809
The coins held by both A and B land heads with probability $\frac{1}{2}$.
- First, A tosses the coin once, and A's victory is decided the moment heads comes up.
- If A's toss is tails, B tosses the coin and can win by getting heads 2 times in a row.
- If B fails to get heads 2 times in a row, both players lose.
Sample 2
Input
2 6 3 0 1 10 2
Output
443664157 0
$M_A$ and $N_A, M_B$ and $N_B$ are not necessarily coprime, respectively. Also, a coin may never land heads.
Sample 3
Input
314159265 358979323 8 27182818 28459045 23 141421356
Output
913236510 968016726
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
Kazun