← 返回题目列表

AtCoder · abc280_e

H. 暴击

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

有一个具有初始体力的怪物 N.
高桥在怪物还有体力的情况下反复攻击怪物 1 或更大。

高桥的攻击使怪物的耐力减少 2 有概率 \frac{P}{100} 和 1 有概率 1-\frac{P}{100}.

求期望值,模 998244353 (参见注释),怪物的体力变为之前的攻击次数 0 或更少。

注释

我们可以证明所求的期望值始终是有限有理数。 而且,在这个问题的约束下,当值表示为 \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

高桥的攻击会降低怪物的耐力 通过 2 有概率 \frac{10}{100}=\frac{1}{10} 和 1 有概率 \frac{100-10}{100}=\frac{9}{10}.

  • 怪物的初始体力为 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