AT_abc280_e [ABC280E] Critical Hit

题目描述

最初有一只体力为 $N$ 的怪兽。
高桥君会不断攻击怪兽，只要怪兽的体力还剩下 $1$ 以上。

高桥君每次攻击，有 $\frac{P}{100}$ 的概率使怪兽体力减少 $2$，有 $1-\frac{P}{100}$ 的概率使怪兽体力减少 $1$。

请输出怪兽体力降为 $0$ 或以下之前，高桥君攻击的期望次数，结果对 $998244353$ 取模（见提示）。

输入格式

输入通过标准输入给出，格式如下：

$N$ $P$

输出格式

请输出高桥君攻击次数的期望值，对 $998244353$ 取模。

输入输出样例 #1

输入 #1

3 10

输出 #1

229596204

输入输出样例 #2

输入 #2

5 100

输出 #2

3

输入输出样例 #3

输入 #3

280 59

输出 #3

567484387

说明/提示

注记

可以证明，所求的期望值一定是有限且为有理数。在本题的约束下，若用互质的两个整数 $P$、$Q$ 表示该值为 $\frac{P}{Q}$，则一定存在唯一的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353}$ 且 $0 \leq R < 998244353$。请输出这个 $R$。

约束条件

• $1 \leq N \leq 2\times 10^5$
• $0 \leq P \leq 100$
• 输入均为整数

样例解释 1

高桥君每次攻击，有 $\frac{10}{100}=\frac{1}{10}$ 的概率使怪兽体力减少 $2$，有 $1-\frac{10}{100}=\frac{9}{10}$ 的概率使怪兽体力减少 $1$。

• 最初怪兽体力为 $3$。
• 第一次攻击后，有 $\frac{9}{10}$ 的概率体力变为 $2$，有 $\frac{1}{10}$ 的概率体力变为 $1$。
• 第二次攻击后，有 $\frac{81}{100}$ 的概率体力变为 $1$，有 $\frac{18}{100}$ 的概率体力变为 $0$，有 $\frac{1}{100}$ 的概率体力变为 $-1$。$\frac{18}{100}+\frac{1}{100}=\frac{19}{100}$ 的概率体力降为 $0$ 或以下，高桥君会在第 $2$ 次攻击后停止。
• 如果第二次攻击后体力还剩 $1$，那么第三次攻击后体力必然降为 $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

高桥君每次攻击总是使怪兽体力减少 $2$。第二次攻击后体力为 $5-2\times 2=1$，还需进行第 $3$ 次攻击。

由 ChatGPT 4.1 翻译