/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
正の整数 N,M が与えられます。k=1,\ldots,N のそれぞれについて、次の問題を解いてください。
- 問題：1 から N の番号がついた 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、人 2 と 4 を同じグループにすることはできません。
- 1 個のグループにすることはできません。
- 2 個のグループにする方法は \{\{1,2\},\{3,4\}\},\{\{1,4\},\{2,3\}\} の 2 通りです。
- 3 個のグループにする方法は \{\{1,2\},\{3\},\{4\}\},\{\{1,4\},\{2\},\{3\}\},\{\{1\},\{2,3\},\{4\}\},\{\{1\},\{2\},\{3,4\}\} の 4 通りです。
- 4 個のグループにする方法は \{\{1\},\{2\},\{3\},\{4\}\} の 1 通りです。
入力例 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 で割ったあまりを求めてください。
Score : 600 points
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.