問題一覧 > 通常問題

No.2685 Cell Proliferation (Easy)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 67
作問者 : ma_twma_tw / テスター : 👑 tute7627tute7627 👑 SPD_9X2SPD_9X2 👑 rin204rin204 だれだれ AyunaAyuna
0 ProblemId : 10444 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-03-21 00:41:44

問題文

この問題は、Cell Proliferation (Hard) と制約および実行時間制限のみが異なります。

AIC細胞は、$t=1,2,...$ に対し、以下の動作を行います。
  • 自らが誕生してからの時間が $t$ 秒になったとき、直ちに確率 $\displaystyle\frac{P_1}{P_2}$ で新たなAIC細胞を $1$ 個誕生させる
  • 自らが誕生してからの時間が $(t + 0.5)$ 秒になったとき、直ちに確率 $\displaystyle1 - \left(\frac{Q_1}{Q_2}\right)^t$ で死んで消滅する
上記の動作以外でAIC細胞の個数が変化することはありません。
今、AIC細胞が $1$ 個だけ誕生しました。現在時刻から $(T + 0.9)$ 秒経過した時刻におけるAIC細胞の個数の期待値を $\mathrm{mod} \ 998244353$ で求めてください。
期待値 $\mathrm{mod} \ 998244353$ の定義
求める期待値は必ず有理数になることが証明できます。またこの問題の制約下において、求める期待値を既約分数 $\displaystyle\frac{P}{Q}$ で表したときに、$Q$ は $998244353$ で割り切れないことが保証されます。 このときある整数 $R$ が唯一つ存在し、$0 \le R < 998244353$ かつ $P \equiv QR \pmod{998244353}$ となります。この $R$ を答えてください。

入力

$P_1 \ P_2 \ Q_1 \ Q_2 \ T$
  • $0 \le P_1 \le P_2 < 998244353, \ P_2 \ne 0$
  • $0 \le Q_1 \le Q_2 < 998244353, \ Q_2 \ne 0$
  • $1 \le T \le 10^3$
  • 入力される値は全て整数

出力

答えを上述の「期待値 $\mathrm{mod} \ 998244353$ の定義」にある通りに出力してください。

サンプル

サンプル1
入力
1 2 3 4 2
出力
577110018

現在時刻から $2.9$ 秒後における期待値は $\displaystyle\frac{91}{64}$ です。$91 \equiv 64 \times 577110018 \pmod{998244353}$ であるため、$577110018$ を出力します。

サンプル2
入力
1 998244352 12345678 23456789 1000
出力
687546754

サンプル3
入力
0 1858 0 2024 166
出力
0

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。