Critical Hit

题目描述

有一只初始耐力为 $N$ 的怪物。
只要怪物的耐力保持在 $1$ 或更高，Takahashi 就会重复攻击该怪物。 Takahashi 的一次攻击以概率 $\frac{P}{100}$ 使怪物的耐力减少 $2$， 以概率 $1-\frac{P}{100}$ 使怪物的耐力减少 $1$。 求怪物的耐力变为 $0$ 或更低之前攻击次数的期望值，对 $998244353$ 取模（参见说明）。

输入格式

输入由标准输入按以下格式给出： $N$ $P$

输出格式

求 Takahashi 的攻击次数的期望值，对 $998244353$ 取模。

3 10

229596204

5 100

3

280 59

567484387

提示

$1 \leq N \leq 2\times 10^5$ $0 \leq P \leq 100$ 输入中的所有值均为整数。我们可以证明所求的期望值总是一个有限的有理数。此外，在本题约束下，当该值表示为互质整数 $P$ 和 $Q$ 的分数 $\frac{P}{Q}$ 时，我们可以证明存在唯一的整数 $R$ 使得 $R \times Q \equiv P\pmod{998244353}$ 且 $0 \leq R \lt 998244353$。输出这样的 $R$。Takahashi 的一次攻击以概率 $\frac{10}{100}=\frac{1}{10}$ 使怪物的耐力减少 $2$， 以概率 $\frac{100-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$ 或更低，Takahashi 在两次攻击后停止攻击。 如果两次攻击后耐力仍为 $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$。
Takahashi 的攻击总是使怪物的耐力减少 $2$。 在第二次攻击后，耐力保持为 $5-2\times 2=1$，所以需要第三次攻击。

标签: AtCoder|abc280E

来源

AtCoder|abc280E