問題一覧 > 通常問題

No.2685 Cell Proliferation (Easy)

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

問題文

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

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

入力

P1 P2 Q1 Q2 TP_1 \ P_2 \ Q_1 \ Q_2 \ T
  • 0≤P1≤P2<998244353, P2≠00 \le P_1 \le P_2 < 998244353, \ P_2 \ne 0
  • 0≤Q1≤Q2<998244353, Q2≠00 \le Q_1 \le Q_2 < 998244353, \ Q_2 \ne 0
  • 1≤T≤1031 \le T \le 10^3
  • 入力される値は全て整数

出力

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

サンプル

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

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

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

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

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