Score : $600$ points

问题描述

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

• 问题：我们将 ID 号从 1 到 $N$ 的 $N$ 个人分成 $k$ 个非空组。这里，ID 号对 $M$ 取模相等的人不能在同一组中。
  • 如何将人分成组的方案有多少种？
  • 由于答案可能非常大，求解结果对 $998244353$ 取模。

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

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

You are given positive integers $N$ and $M$. For each $k=1,\ldots,N$, solve the following problem.

• Problem: We will divide $N$ people with ID numbers $1$ through $N$ into $k$ non-empty groups. Here, people whose ID numbers are equal modulo $M$ cannot belong to the same group.
  How many such ways are there to divide people into groups?
  Since the answer may be enormous, find it modulo $998244353$.

Here, two ways to divide people into groups are considered different when there is a pair $(x, y)$ such that Person $x$ and Person $y$ belong to the same group in one way but not in the other.

Constraints

• $2 \leq N \leq 5000$
• $2 \leq M \leq N$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $M$

Output

Print $N$ lines.

The $i$-th line should contain the answer for the problem with $k=i$.

Sample Input 1

4 2

Sample Output 1

0
2
4
1

People whose ID numbers are equal modulo $2$ cannot belong to the same group. That is, Person $1$ and Person $3$ cannot belong to the same group, and neither can Person $2$ and Person $4$.

• There is no way to divide the four into one group.
• There are two ways to divide the four into two groups: $\{\{1,2\},\{3,4\}\}$ and $\{\{1,4\},\{2,3\}\}$.
• There are four ways to divide the four into three groups: $\{\{1,2\},\{3\},\{4\}\}$, $\{\{1,4\},\{2\},\{3\}\}$, $\{\{1\},\{2,3\},\{4\}\}$, and $\{\{1\},\{2\},\{3,4\}\}$.
• There is one way to divide the four into four groups: $\{\{1\},\{2\},\{3\},\{4\}\}$.

Sample Input 2

6 6

Sample Output 2

1
31
90
65
15
1

You can divide them as you like.

Sample Input 3

20 5

Sample Output 3

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

Be sure to find the answer modulo $998244353$.

update @ 2024/3/10 09:37:40