分数: 1300 点
问题陈述
有 N 人数 1 通过 N,和 K 项目编号 1 通过 K。 他们玩回合制游戏。 人 1 进行第一回合,Person 2 进行下一个回合,然后是人 3, \ldots, 人 N,然后是人 再次 1 , \ldots, 人 N, 人 1 , \ldots,依此类推,直到所有物品都被拿走。
每回合都会发生以下情况:
- 如果此人已经赢得了物品,则不会发生任何事情。
- 否则,他会随机选择一个他还没有统一选择的项目,并偷偷告诉游戏的裁判Snuke。 如果该物品已被其他人拿走,则不会发生任何事情;否则他就赢得了该物品。
对于每个 i,计算 Person 的概率 i 赢得一个项目,取模 998,244,353 (如注释部分所述)。
注释
- 所有随机选择都是独立做出的。
- 我们可以证明游戏总是以有限步数结束。
- 我们还可以证明,每当玩家被要求选择一个项目时,他至少有一个尚未选择的项目。
- 我们还可以证明概率是有理数。当你打印概率时,首先把它写成分数 \frac{y}{x},其中 x, y 是整数并且 x 不能被整除 P = 998,244,353 (在问题的约束下,这种表示总是可能的)。 然后,您需要打印唯一的整数 z 之间 0 和 P - 1,包含在内,满足 xz \equiv y \pmod{P}.
约束
- 1 \leq K \leq N \leq 40
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N K
输出
打印 N 行。 上 i第行,打印 i- 第人赢得一个物品,取模 998,244,353.
示例输入 1
3 2
示例输出 1
1 249561089 748683265
- 第一,人 1 选择一个项目(将其称为 Item p),并获胜。
- 然后,与 1/2 概率,人 2 在下一回合中选择另一个项目并获胜,游戏结束。
- 与 1/2 概率,人 2 选择 p,他没有赢,而 Person 3 进行下一个回合。
- 与 1/4 概率,人 3 选择另一个项目,获胜,游戏结束。 再次
- 与 1/4 概率,人 3 选择 p 。然后,下一个回合是人 1没有任何反应,因为他已经赢得了一件物品。然后,在下一个回合中,Person 2 肯定选择其他项目,因为他已经选择了 p 在他的上一个回合中,所以他这次赢得了一个物品,游戏结束。
总结一下,人 1, 2, 3 将有概率获得物品 1, \frac{3}{4}, \frac{1}{4}。
示例输入 2
4 3
示例输出 2
1 314262112 767169272 915057324
概率是 1, \frac{47}{54}, \frac{77}{108}, \frac{5}{12}.
示例输入 3
40 10
示例输出 3
1 868517173 27621563 837064957 222682471 512462123 662169358 927654899 421237429 47896491 462367772 888812171 300869511 63754652 144548024 358216674 895724239 274552277 722622637 946769993 579325471 777654313 142897955 607284898 8038340 863909530 63295741 862961672 335905745 944425523 358698956 299986928 847582651 197657467 180361665 412489246 762713624 410322243 646538576 79047758