102804: [AtCoder]ABC280 E - Critical Hit

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

问题描述

有一个初始体力为$N$的怪物。
当怪物的体力仍然为1或更大时，高桥反复攻击怪物。

高桥的攻击以$\frac{P}{100}$的概率减少怪物的体力2，以概率$1-\frac{P}{100}$减少怪物的体力1。

求在怪物的体力变为0或更小之前，高桥的攻击次数的期望值（见注释），结果对998244353取模。

注释

我们可以证明所求的期望值总是有限的有理数。此外，在本问题的约束下，当值表示为$\frac{P}{Q}$，其中$P$和$Q$为互质的整数时，我们可以证明存在一个整数$R$，使得$R \times Q \equiv P\pmod{998244353}$且$0 \leq R \lt 998244353$。输出这样的$R$。

约束

• $1 \leq N \leq 2\times 10^5$
• $0 \leq P \leq 100$
• 输入中的所有值都是整数。

输入

输入从标准输入给出以下格式：

$N$ $P$

输出

求高桥攻击次数的期望值，结果对998244353取模。

样例输入1

3 10

样例输出1

229596204

高桥的攻击以$\frac{10}{100}=\frac{1}{10}$的概率减少怪物的体力2，以概率$\frac{100-10}{100}=\frac{9}{10}$减少怪物的体力1。

• 怪物的初始体力为$3$。
• 第一次攻击后，怪物的体力为$2$的概率为$\frac{9}{10}$，为$1$的概率为$\frac{1}{10}$。
• 第二次攻击后，怪物的体力为$1$的概率为$\frac{81}{100}$，为$0$的概率为$\frac{18}{100}$，为$-1$的概率为$\frac{1}{100}$。以$\frac{18}{100}+\frac{1}{100}=\frac{19}{100}$的概率，体力变为0或更小，高桥在两次攻击后停止攻击。
• 如果两次攻击后体力仍然为$1$，怪物的体力总会在第三次攻击时变为0或更小，所以他会在三次攻击后停止攻击。

因此，期望值为$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

高桥的攻击总是减少怪物的体力2。第二次攻击后，体力变为$5-2\times 2=1$，所以需要第三次攻击。

样例输入3

280 59

样例输出3

567484387