atcoder#ABC280E. [ABC280E] Critical Hit
[ABC280E] Critical Hit
题目描述
最初、体力が であるモンスターが 体います。
高橋君はモンスターに対し、モンスターの体力が 以上残っている限り繰り返し攻撃を行います。
高橋君は 回の攻撃で、 の確率でモンスターの体力を 減らし、 の確率でモンスターの体力を 減らします。
モンスターの体力が 以下になるまでに行う攻撃回数の期待値を で出力してください(注記参照)。
输入格式
入力は以下の形式で標準入力から与えられる。
输出格式
高橋君の攻撃回数の期待値を で出力せよ。
题目大意
这里有一个 滴血的怪物。每一次攻击你有 的概率让它失去 滴血,有 的概率让它失去 滴血。如果攻击过后怪物的血量 ,它就死了。你需要一直攻击怪物直到它死亡。输出攻击次数的期望对 取模的值。
对有理数的取模见 洛谷 P2613。
3 10
229596204
5 100
3
280 59
567484387
提示
注記
求める期待値は必ず有限値かつ有理数となることが証明できます。また、この問題の制約下では、その値を互いに素な つの整数 , を用いて と表したとき、 かつ を満たす整数 がただ一つ存在することが証明できます。この を出力してください。
制約
- 入力は全て整数
Sample Explanation 1
高橋君は 回の攻撃で、 の確率でモンスターの体力を 減らし、 の確率でモンスターの体力を 減らします。 - 最初、モンスターの体力は です。 - 回目の攻撃の後、の確率でモンスターの体力は 、の確率でモンスターの体力は となります。 - 回目の攻撃の後、の確率でモンスターの体力は 、 の確率でモンスターの体力は 、 の確率でモンスターの体力は となります。 の確率で体力は 以下となり、高橋君は 回で攻撃をやめます。 - 回目の攻撃の後で体力が 残っている場合、 回目の攻撃の後でモンスターの体力は必ず 以下となり、高橋君は 回で攻撃をやめます。 よって、期待値は $ 2\times\ \frac{19}{100}+3\times\left(1-\frac{19}{100}\right)=\frac{281}{100} $ となります。$ 229596204\ \times\ 100\ \equiv\ 281\pmod{998244353} $ であるため、 を出力します。
Sample Explanation 2
高橋君は 回の攻撃で、つねにモンスターの体力を 減らします。 回目の攻撃が終わった時点では体力が 残っているため、 回目の攻撃を行う必要があります。