問題一覧 > 通常問題

No.1547 [Cherry 2nd Tune *] Probability of a Chance Victory

レベル : / AI推定難易度 : 1750 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 44
作問者 : 👑 Kazun / テスター : 👑 qand
お気に入りにしたユーザー ProblemId : 6275 / 自分の提出
問題文最終更新日: 2021-06-14 02:56:42
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 299 (BANNED CONTEST) (順位表) の他の問題:

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.

  1. Assign $0$ to the variables $X,Y$.
  2. A tosses their coin.
  3. 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.
  4. B tosses their coin.
  5. 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.
  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.

Therefore, $\alpha=\frac{1}{2}, \beta=\frac{1}{8}$, so $\alpha \pmod{998244353}=499122177, \beta \pmod{998244353}=873463809$.
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もしくは右上の雲マークをクリックしてアカウントを作成してください。