Groups

题目描述

给定正整数 $N$ 和 $M$。对于每个 $k=1,\ldots,N$，求解以下问题。

问题：我们将编号为 $1$ 到 $N$ 的 $N$ 个人分成 $k$ 个非空组。 在这里，编号对 $M$ 取模相等的人不能属于同一组。
有多少种这样的分组方式？
由于答案可能非常大，请对 $998244353$ 取模。

这里，当存在一对 $(x, y)$ 使得在一种分组方式中人 $x$ 和人 $y$ 属于同一组但在另一种方式中不属于同一组时，这两种分组方式被认为是不同的。

输入格式

输入按标准输入给出，格式如下： $N$ $M$

输出格式

输出 $N$ 行。 第 $i$ 行应包含参数 $k=i$ 的问题的答案。

4 2

0
2
4
1

6 6

1
31
90
65
15
1

20 5

0
0
0
331776
207028224
204931064
814022582
544352515
755619435
401403040
323173195
538468102
309259764
722947327
162115584
10228144
423360
10960
160
1

提示

$2 \leq N \leq 5000$ $2 \leq M \leq N$ 输入中的所有数均为整数。编号对 $2$ 取模相等的人不能属于同一组。也就是说，1 号和 3 号不能属于同一组，2 号和 4 号也不能属于同一组。

无法将四个人分成一个组。 将四个人分成两个组有两种方法：$\{\{1,2\},\{3,4\}\}$ 和 $\{\{1,4\},\{2,3\}\}$。 将四个人分成三个组有四种方法：$\{\{1,2\},\{3\},\{4\}\}$、$\{\{1,4\},\{2\},\{3\}\}$、$\{\{1\},\{2,3\},\{4\}\}$ 和 $\{\{1\},\{2\},\{3,4\}\}$。 将四个人分成四个组有一种方法：$\{\{1\},\{2\},\{3\},\{4\}\}$。
你可以随意分组。
请务必对 $998244353$ 取模。

标签: AtCoder|abc217G

来源

AtCoder|abc217G