G - 分组

得分 : $600$ 点

题目描述

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

• 问题：将 ID 号从 $1$ 到 $N$ 的 $N$ 个人分成 $k$ 个非空组。 这里，ID 号模 $M$ 相等的人不能属于同一组。
  有多少种方式可以将人分成组？
  由于答案可能很大，对 $998244353$ 取模。

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

约束条件

• $2 \leq N \leq 5000$
• $2 \leq M \leq N$
• 输入中的所有值为整数。

输入

从标准输入读入以下格式的输入。

$N$ $M$

输出

输出一个包含 $N$ 行的结果。

第 $i$ 行应该包含问题 $k=i$ 的答案。

4 2

0
2
4
1

ID 号模 $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\}\}$。

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

请确保对 $998244353$ 取模。