/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
最初、体力が N であるモンスターが 1 体います。
高橋君はモンスターに対し、モンスターの体力が 1 以上残っている限り繰り返し攻撃を行います。
高橋君は 1 回の攻撃で、\frac{P}{100} の確率でモンスターの体力を 2 減らし、 1-\frac{P}{100} の確率でモンスターの体力を 1 減らします。
モンスターの体力が 0 以下になるまでに行う攻撃回数の期待値を \text{mod } 998244353 で出力してください（注記参照）。
注記
求める期待値は必ず有限値かつ有理数となることが証明できます。また、この問題の制約下では、その値を互いに素な 2 つの整数 P, Q を用いて \frac{P}{Q} と表したとき、R \times Q \equiv P\pmod{998244353} かつ 0 \leq R \lt 998244353 を満たす整数 R がただ一つ存在することが証明できます。この R を出力してください。
制約
- 1 \leq N \leq 2\times 10^5
- 0 \leq P \leq 100
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N P
出力
高橋君の攻撃回数の期待値を \text{mod } 998244353 で出力せよ。
入力例 1
3 10
出力例 1
229596204
高橋君は 1 回の攻撃で、 \frac{10}{100}=\frac{1}{10} の確率でモンスターの体力を 2 減らし、 1-\frac{10}{100}=\frac{9}{10} の確率でモンスターの体力を 1 減らします。
- 最初、モンスターの体力は 3 です。
- 1 回目の攻撃の後、\frac{9}{10}の確率でモンスターの体力は 2、\frac{1}{10}の確率でモンスターの体力は 1 となります。
- 2 回目の攻撃の後、\frac{81}{100}の確率でモンスターの体力は 1、\frac{18}{100} の確率でモンスターの体力は 0、\frac{1}{100} の確率でモンスターの体力は -1 となります。 \frac{18}{100}+\frac{1}{100}=\frac{19}{100} の確率で体力は 0 以下となり、高橋君は 2 回で攻撃をやめます。
- 2 回目の攻撃の後で体力が 1 残っている場合、3 回目の攻撃の後でモンスターの体力は必ず 0 以下となり、高橋君は 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 を出力します。
入力例 2
5 100
出力例 2
3
高橋君は 1 回の攻撃で、つねにモンスターの体力を 2 減らします。 2 回目の攻撃が終わった時点では体力が 5-2\times 2=1 残っているため、3 回目の攻撃を行う必要があります。
入力例 3
280 59
出力例 3
567484387
Score : 500 points
Problem Statement
There is a monster with initial stamina N.
Takahashi repeatedly attacks the monster while the monster's stamina remains 1 or greater.
An attack by Takahashi reduces the monster's stamina by 2 with probability \frac{P}{100} and by 1 with probability 1-\frac{P}{100}.
Find the expected value, modulo 998244353 (see Notes), of the number of attacks before the monster's stamina becomes 0 or less.
Notes
We can prove that the sought expected value is always a finite rational number. Moreover, under the Constraints of this problem, when the value is represented as \frac{P}{Q} by two coprime integers P and Q, we can show that there exists a unique integer R such that R \times Q \equiv P\pmod{998244353} and 0 \leq R \lt 998244353. Print such R.
Constraints
- 1 \leq N \leq 2\times 10^5
- 0 \leq P \leq 100
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N P
Output
Find the expected value, modulo 998244353, of the number of Takahashi's attacks.
Sample Input 1
3 10
Sample Output 1
229596204
An attack by Takahashi reduces the monster's stamina by 2 with probability \frac{10}{100}=\frac{1}{10} and by 1 with probability \frac{100-10}{100}=\frac{9}{10}.
- The monster's initial stamina is 3.
- After the first attack, the monster's stamina is 2 with probability \frac{9}{10} and 1 with probability \frac{1}{10}.
- After the second attack, the monster's stamina is 1 with probability \frac{81}{100}, 0 with probability \frac{18}{100}, and -1 with probability \frac{1}{100}. With probability \frac{18}{100}+\frac{1}{100}=\frac{19}{100}, the stamina becomes 0 or less, and Takahashi stops attacking after two attacks.
- If the stamina remains 1 after two attacks, the monster's stamina always becomes 0 or less by the third attack, so he stops attacking after three attacks.
Therefore, the expected value is 2\times \frac{19}{100}+3\times\left(1-\frac{19}{100}\right)=\frac{281}{100}. Since 229596204 \times 100 \equiv 281\pmod{998244353}, print 229596204.
Sample Input 2
5 100
Sample Output 2
3
Takahashi's attack always reduces the monster's stamina by 2. After the second attack, the stamina remains 5-2\times 2=1, so the third one is required.
Sample Input 3
280 59
Sample Output 3
567484387