← 返回题目列表

AtCoder · abc217_g

G. 组

中文机器翻译题面 查看原题

分数: 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.