atcoder#ABC280E. [ABC280E] Critical Hit

[ABC280E] Critical Hit

题目描述

最初、体力が N N であるモンスターが 1 1 体います。
高橋君はモンスターに対し、モンスターの体力が 1 1 以上残っている限り繰り返し攻撃を行います。

高橋君は 1 1 回の攻撃で、P100 \frac{P}{100} の確率でモンスターの体力を 2 2 減らし、 1P100 1-\frac{P}{100} の確率でモンスターの体力を 1 1 減らします。

モンスターの体力が 0 0 以下になるまでに行う攻撃回数の期待値を mod  998244353 \text{mod\ }\ 998244353 で出力してください(注記参照)。

输入格式

入力は以下の形式で標準入力から与えられる。

N N P P

输出格式

高橋君の攻撃回数の期待値を mod  998244353 \text{mod\ }\ 998244353 で出力せよ。

题目大意

这里有一个 nn 滴血的怪物。每一次攻击你有 P%P\% 的概率让它失去 22 滴血,有 (100P)%(100-P)\% 的概率让它失去 11 滴血。如果攻击过后怪物的血量 0\leq 0,它就死了。你需要一直攻击怪物直到它死亡。输出攻击次数的期望对 998244353998244353 取模的值。

1n2×105,0P1001\leq n\leq 2\times10^5,0\leq P\leq 100

对有理数的取模见 洛谷 P2613

3 10
229596204
5 100
3
280 59
567484387

提示

注記

求める期待値は必ず有限値かつ有理数となることが証明できます。また、この問題の制約下では、その値を互いに素な 2 2 つの整数 P P , Q Q を用いて PQ \frac{P}{Q} と表したとき、R × Q  P(mod998244353) R\ \times\ Q\ \equiv\ P\pmod{998244353} かつ 0  R < 998244353 0\ \leq\ R\ \lt\ 998244353 を満たす整数 R R がただ一つ存在することが証明できます。この R R を出力してください。

制約

  • 1  N  2× 105 1\ \leq\ N\ \leq\ 2\times\ 10^5
  • 0  P  100 0\ \leq\ P\ \leq\ 100
  • 入力は全て整数

Sample Explanation 1

高橋君は 1 1 回の攻撃で、 10100=110 \frac{10}{100}=\frac{1}{10} の確率でモンスターの体力を 2 2 減らし、 110100=910 1-\frac{10}{100}=\frac{9}{10} の確率でモンスターの体力を 1 1 減らします。 - 最初、モンスターの体力は 3 3 です。 - 1 1 回目の攻撃の後、910 \frac{9}{10} の確率でモンスターの体力は 2 2 110 \frac{1}{10} の確率でモンスターの体力は 1 1 となります。 - 2 2 回目の攻撃の後、81100 \frac{81}{100} の確率でモンスターの体力は 1 1 18100 \frac{18}{100} の確率でモンスターの体力は 0 0 1100 \frac{1}{100} の確率でモンスターの体力は 1 -1 となります。 18100+1100=19100 \frac{18}{100}+\frac{1}{100}=\frac{19}{100} の確率で体力は 0 0 以下となり、高橋君は 2 2 回で攻撃をやめます。 - 2 2 回目の攻撃の後で体力が 1 1 残っている場合、3 3 回目の攻撃の後でモンスターの体力は必ず 0 0 以下となり、高橋君は 3 3 回で攻撃をやめます。 よって、期待値は $ 2\times\ \frac{19}{100}+3\times\left(1-\frac{19}{100}\right)=\frac{281}{100} $ となります。$ 229596204\ \times\ 100\ \equiv\ 281\pmod{998244353} $ であるため、229596204 229596204 を出力します。

Sample Explanation 2

高橋君は 1 1 回の攻撃で、つねにモンスターの体力を 2 2 減らします。 2 2 回目の攻撃が終わった時点では体力が 52× 2=1 5-2\times\ 2=1 残っているため、3 3 回目の攻撃を行う必要があります。