No.1547 [Cherry 2nd Tune *] 偶然の勝利の確率
タグ : / 解いたユーザー数 43
作問者 : 👑
Kazun
/ テスター :
遭難者
お詫び
コンテスト出題時において, 2021/06/11 22:33 頃まで制約違反のテストケースが存在していることが判明しました. 制約に適するテストケースに訂正し, リジャッジした所, 5名について本来ならば正解にすべき所, 制約違反が原因である不正解判定を受けていることがわかりました. 該当者へお詫びを申し上げます.問題文
A と B の2人が以下のゲームを行う. ここで, A, Bはそれぞれ表が出る確率が $\frac{M_A}{N_A}, \frac{M_B}{N_B}$ であるコインを持っている.
このコインを用いて以下のゲームを行う.
- 変数 $X,Y$ に $0$ を代入する.
- A は自分が持っているコインを投げる.
- 投げたコインの表裏によって以下の行動を行う.
- 表だった場合, $X$ に $1$ を加える. その後, $X=S$ ならば直ちにゲームを終了させ, A の勝利, B の敗北とする. $X < S$ ならば 2. に戻る.
- 裏だった場合, 4.に進む.
- B は自分が持っているコインを投げる.
- 投げたコインの表裏によって以下の行動を行う.
- 表だった場合, $X$ から $1$ を減らす. その後, $X=-T$ ならば直ちにゲームを終了させ, B の勝利, A の敗北とする. $X > -T$ ならば 4. に戻る.
- 裏だった場合, 6.に進む.
- $Y$ に $1$ を加える. その後, $Y < K$ ならば2.に戻る. $Y=K$ ならば, ゲームは終了となり, A, B 共に敗北となる.
ただし, A, B が持っているコインは投げると, 表か裏のうち一方のみが出る.
このゲームにおいて, A, Bが勝利となる確率をそえれぞれ $\alpha, \beta$ としたとき, $\alpha \pmod{998244353}, \beta \pmod{998244353}$ を求めよ.
なお, この問題の制約下では $\alpha, \beta$ は共に有理数になることが証明できる.
▶(有理数)$\pmod{998244353}$ とは
この問題の制約下において, 出力すべき有理数 $H$ は整数 $P$ と $998244353$ の倍数ではない整数 $Q$ を用いて, $H=\frac{P}{Q}$ と表すことができることが保証されている. このとき, $P \equiv QX~\pmod{998244353}$ を満たす $0$ 以上 $998244353$ 未満の整数 $X$ が唯一存在するので, この整数 $X$ を用いて, $H \pmod{998244353}=X$ と定義する.
制約
- $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$
- 入力は全て整数である.
入力
$M_A$ $N_A$ $S$ $M_B$ $N_B$ $T$ $K$
出力
出力は $2$ 行からなる. A, B が勝利する確率を $\alpha, \beta$ としたとき, $1$ 行目には $\alpha \pmod{998244353}$, $2$ 行目には $\beta \pmod{998244353}$ を出力せよ. 改行を忘れないこと.
サンプル
サンプル1
入力
1 2 1 1 2 2 1
出力
499122177 873463809
A, Bの両者が持っているコインは $\frac{1}{2}$ の確率で表が出る.
- 最初 A がコインを1回投げ, 表が出た瞬間 A の勝利が確定する.
- A が投げたコインが裏だった場合, B がコインを投げ, 2回連続で表を出すことで勝利することができる.
- B が2回連続で表を出せなかった場合, 両者とも敗北になる.
サンプル2
入力
2 6 3 0 1 10 2
出力
443664157 0
$M_A$ と $N_A, M_B$ と $N_B$ はそれぞれ互いに素とは限らない. また, コインは表が出ないかもしれない.
サンプル3
入力
314159265 358979323 8 27182818 28459045 23 141421356
出力
913236510 968016726
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。