H - Count Multiset Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

正の整数 N, M が与えられます。

k=1,2,\ldots,N について以下の値を求め、998244353 で割ったあまりをそれぞれ出力してください。

  • k 個の正整数からなる多重集合 A のうち、以下の 2 つの条件をすべて満たすものの個数
    • A に含まれる要素の総和は N
    • 任意の正整数 x について、A は x を高々 M 個しか含まない

制約

  • 1 \leq M \leq N \leq 5000
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N M

出力

N 行に渡って出力せよ。i\ (1 \leq i \leq N) 行目には、k=i の場合の答えを出力すること。

入力例 1

4 2

出力例 1

1
2
1
0
  • k=1 のとき、問題文中の条件を満たすような多重集合 A は \{4\} の 1 通りです。
  • k=2 のとき、問題文中の条件を満たすような多重集合 A は \{1,3\} と \{2,2\} の 2 通りです。
  • k=3 のとき、問題文中の条件を満たすような多重集合 A は \{1,1,2\} の 1 通りです。
  • k=4 のとき、問題文中の条件を満たすような多重集合 A は 1 つも存在しません。

入力例 2

7 7

出力例 2

1
3
4
3
2
1
1

Score : 600 points

Problem Statement

Given are positive integers N and M.

For each k=1,2,\ldots,N, find the following number and print it modulo 998244353.

  • The number of multisets A containing k positive integers that satisfy both of the following conditions:
    • the sum of the elements of A is N;
    • for every positive integer x, A contains at most M occurrences of x.

Constraints

  • 1 \leq M \leq N \leq 5000
  • 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 (1 \leq i \leq N) should contain the answer for the case k=i.

Sample Input 1

4 2

Sample Output 1

1
2
1
0
  • For k=1, there is one multiset A that satisfies the conditions: \{4\}.
  • For k=2, there are two multisets A that satisfy the conditions: \{1,3\} and \{2,2\}.
  • For k=3, there is one multiset A that satisfies the conditions: \{1,1,2\}.
  • For k=4, there is no multiset A that satisfies the conditions.

Sample Input 2

7 7

Sample Output 2

1
3
4
3
2
1
1