← 返回题目列表

AtCoder · abc409_g

G. 财富积累

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

分数: 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