AT_abc217_g [ABC217G] Groups

题目描述

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

• 问题：将编号为 $1$ 到 $N$ 的 $N$ 个人分成 $k$ 个非空小组。要求编号对 $M$ 取模余数相同的人不能被分到同一个小组。 这样的分组方法有多少种？ 由于答案可能非常大，请输出对 $998244353$ 取模的结果。

这里，若存在某一对 $(x, y)$，使得在一种分组中 $x, y$ 在同一组，而在另一种分组中 $x, y$ 不在同一组，则认为这两种分组不同。

输入格式

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

$N$ $M$

输出格式

输出 $N$ 行。

第 $i$ 行输出 $k=i$ 时问题的答案。

输入输出样例 #1

输入 #1

4 2

输出 #1

0
2
4
1

输入输出样例 #2

输入 #2

6 6

输出 #2

1
31
90
65
15
1

输入输出样例 #3

输入 #3

20 5

输出 #3

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$
• 输入均为整数

样例解释 1

编号对 $2$ 取模余数相同的人，即 $1$ 和 $3$，$2$ 和 $4$，不能被分到同一组。

• 分成 $1$ 个组是不可能的。
• 分成 $2$ 个组的方法有 $2$ 种：$\{\{1,2\},\{3,4\}\},\{\{1,4\},\{2,3\}\}$。
• 分成 $3$ 个组的方法有 $4$ 种：$\{\{1,2\},\{3\},\{4\}\},\{\{1,4\},\{2\},\{3\}\},\{\{1\},\{2,3\},\{4\}\},\{\{1\},\{2\},\{3,4\}\}$。
• 分成 $4$ 个组的方法有 $1$ 种：$\{\{1\},\{2\},\{3\},\{4\}\}$。

样例解释 2

可以自由分组。

样例解释 3

请输出对 $998244353$ 取模的答案。

由 ChatGPT 4.1 翻译