H - Count Multiset
解説
/
実行時間制限: 2 sec / メモリ制限: 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