No.2685 Cell Proliferation (Easy)
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 72
作問者 :
ma_tw
/ テスター :
👑 
tute7627
👑 
SPD_9X2
👑 
rin204
だれ
Ayuna
タグ : / 解いたユーザー数 72
作問者 :
ma_tw
/ テスター :
👑 tute7627
👑 SPD_9X2
👑 rin204
だれ
Ayuna
問題文最終更新日: 2024-03-21 00:41:44
問題文
この問題は、Cell Proliferation (Hard) と制約および実行時間制限のみが異なります。
- 自らが誕生してからの時間が $t$ 秒になったとき、直ちに確率 $\displaystyle\frac{P_1}{P_2}$ で新たなAIC細胞を $1$ 個誕生させる
- 自らが誕生してからの時間が $(t + 0.5)$ 秒になったとき、直ちに確率 $\displaystyle1 - \left(\frac{Q_1}{Q_2}\right)^t$ で死んで消滅する
今、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もしくは右上の雲マークをクリックしてアカウントを作成してください。