← 返回题目列表

AtCoder · agc050_d

D. 购物

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

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