[agc050_d]Shopping

ID: 2003

传统题

4000ms

1024MiB

尝试: 0

已通过: 0

难度: 8

上传者:

admin

标签>

2600+

问题描述

有 $N$ 个编号为 $1$ 到 $N$ 的人和 $K$ 个编号为 $1$ 到 $K$ 的物品。他们玩一个逐轮进行的游戏。第一轮是第 $1$ 个人，第二轮是第 $2$ 个人，然后是第 $3$ 个人， $\\ldots$ ，直到第 $N$ 个人，然后又是第 $1$ 个人， $\\ldots$ ，以此类推，直到所有物品都被拿走。

在每一轮中，发生以下情况：

如果这个人已经获得了一个物品，则不发生任何事情。
否则，他从尚未选择的物品中随机选择一个，并将其秘密告诉游戏的裁判Snuke。如果该物品已被其他人拿走，什么也不会发生；否则他就赢得了这个物品。

对于每个 $i$ ，计算第 $i$ 个人获胜的概率，取模 $998,244,353$ （如“注释”部分所述）。

注释

所有随机选择都是独立的。
我们可以证明游戏总是在有限的步数内结束。
我们还可以证明，每当玩家被要求选择一个物品时，他至少有一个他还没有选择的物品。
我们还可以证明这些概率是有理数。当打印概率时，首先将其写成分数 $\\frac{y}{x}$ 的形式，其中 $x, y$ 是整数， $x$ 不能被 $P = 998,244,353$ 整除（在问题的约束条件下，这种表示总是可能的）。然后，你需要打印一个整数 $z$ ，满足 $xz \\equiv y \\pmod{P}$ ，且 $0 \\leq z < P - 1$ 。

约束条件

$1 \\leq K \\leq N \\leq 40$
输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$N$ $K$

输出

打印 $N$ 行。第 $i$ 行，打印第 $i$ 个人获胜的概率，取模 $998,244,353$ 。

示例输入 1

3 2

示例输出 1

1
249561089
748683265

首先，第 $1$ $1$ 个人选择一个物品（称之为物品 $p$ $p$ ）并赢得它。
- 然后，有 $1/2$ 的概率，第 $2$ 个人在下一轮选择另一个物品并赢得它，游戏结束。
- 有 $1/2$ $1/2$ 的概率，第 $2$ $2$ 个人选择 $p$ $p$ ，他没有赢得它，然后第 $3$ $3$ 个人轮到。
  - 有 $1/4$ 的概率，第 $3$ 个人选择另一个物品，赢得它，游戏结束。
  - 有 $1/4$ 的概率，第 $3$ 个人再次选择 $p$ 。然后，下一轮是第 $1$ 个人的轮次，因为他已经赢得了一个物品，所以什么也不发生。然后，在下一轮中，第 $2$ 个人肯定会选择另一个物品，因为他在上一轮中已经选择了 $p$ ，所以他这一次赢得了一个物品，游戏结束。

综上所述，第 $1, 2, 3$ 个人获得物品的概率分别为 $1, \\frac{3}{4}, \\frac{1}{4}$ 。

示例输入 2

4 3

示例输出 2

这些概率是 $1, \\frac{47}{54}, \\frac{77}{108}, \\frac{5}{12}$ 。

示例输入 3

40 10

示例输出 3

#agc050d. [agc050_d]Shopping