分数: 600 点
问题陈述
给你正整数 N 和 M。对于每个 k=1,\ldots,N,解决以下问题。
- 问题:我们将划分 N 有身份证号码的人 1 通过 N 进入 k 非空组。
这里,身份证号码模数相等的人 M 不能属于同一组。
有多少种这样的将人们分组的方法?
由于答案可能很大,请对它求模 998244353.
这里,当有一对时,两种将人分组的方法被认为是不同的 (x, y) 这样的人 x 和人 y 在一种方面属于同一组,但在另一种方面不属于同一组。
约束
- 2 \leq N \leq 5000
- 2 \leq M \leq N
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M
输出
打印 N 行。
的 i- 第行应包含问题的答案 k=i.
示例输入 1
4 2
示例输出 1
0 2 4 1
身份证号码模数相等的人 2 不能属于同一组。也就是说,人 1 和人 3 不能属于同一组,Person 也不能属于同一组 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\}\}.
示例输入 2
6 6
示例输出 2
1 31 90 65 15 1
您可以根据需要划分它们。
示例输入 3
20 5
示例输出 3
0 0 0 331776 207028224 204931064 814022582 544352515 755619435 401403040 323173195 538468102 309259764 722947327 162115584 10228144 423360 10960 160 1
一定要找到模数的答案 998244353.