分数: 625 点
问题陈述
给你一个整数 N \geq 2 和一个整数 P 之间 0 和 100,包括在内。让 p=P/100.
有一个序列 A。最初,长度为 A is 1,其唯一元素是 1.
重复以下操作 N-1 次顺序 A:
- 让 m 是未出现在中的最小正整数 A。有概率 p,执行操作 1;有概率 1-p,执行操作 2:
- 操作 1:追加 m 到年底 A.
- 操作 2:让 c_1,c_2,\dots,c_{m-1} 是次数 1,2,\dots,m-1 出现在 分别是 A。选择一个整数 k 之间 1 和 m-1,包含在内,概率与 c_k。也就是说,选择 k 有概率 c_k/\sum_{j=1}^{m-1} c_j。然后,追加 k 到年底 A.
对于每个 k=1,2,\dots,N,找到预期出现的次数 k in A 之后 N-1 运算,模数 998244353.
期望值模的定义 998244353
可以证明,你求的期望值总是有理数。并且,在这个问题的约束下,可以证明,当这个值表示为不可约分数时 \frac{P}{Q},我们有 Q {{}\not\equiv{}} 0 \pmod{998244353}。因此,存在一个唯一的整数 R 这样 R \times Q \equiv P \pmod{998244353} 和 0 \leq R \lt 998244353。输出这个 R.
约束
- 2 \leq N \leq 10^5
- 0 \leq P \leq 100
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N P
输出
输出 N 行。的 k-th (1\leq k \leq N) 行应包含预期出现的次数 k in A 运算后,取模 998244353.
示例输入 1
3 50
示例输出 1
124780546 124780545 748683265
操作过程如下:
- 最初, 黑板上写着 A=(1).
- 1st操作:变成 A=(1,2) 有概率 1/2,和 A=(1,1) 有概率 1/2.
- 2第二次操作:
- If A=(1,2),它变成 A=(1,2,3) 有概率 1/2, A=(1,2,1) 有概率 1/4,和 A=(1,2,2) 有概率 1/4.
- If A=(1,1),它变成 A=(1,1,2) 有概率 1/2,和 A=(1,1,1) 有概率 1/2.
的预期出现次数 1,2,3 在决赛中 A 是 \frac{15}{8}, \frac{7}{8}, \frac{1}{4}。
示例输入 2
2 0
示例输出 2
2 0
示例输入 3
5 24
示例输出 3
297734288 442981554 937492320 798158491 518366411