102217: [AtCoder]ABC221 H - Count Multiset

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

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

Input

题意翻译

输入两个正整数 $N,M$，并存在一个集合，问你一个长度为 $k$ 的合法集合存在多少个？你需要回答 $k$ 的值为 $1$ 到 $N$ 的每种情况。 一个合法的集合定义指长度为 $k$，元素和为 $N$，每一个数字在集合中出现的次数都小于等于 $M$ 的集合。

Output

分数：600分

问题描述

给定两个正整数N和M。

对于每个k=1,2,...,N，找出以下数字并将其模998244353输出。

  • 满足以下两个条件的含有k个正整数的多重集合A的数量：
    • A的元素和为N；
    • 对于每个正整数x，A中x的出现次数最多为M。

约束条件

  • 1≤M≤N≤5000
  • 输入中的所有值都是整数。

输入

输入通过标准输入以以下格式给出：

$N$ $M$

输出

输出N行；第i行(1≤i≤N)应包含k=i时的答案。

样例输入1

4 2

样例输出1

1
2
1
0
  • 对于k=1，存在一个满足条件的多重集合A：{4}。
  • 对于k=2，存在两个满足条件的多重集合A：{1,3}和{2,2}。
  • 对于k=3，存在一个满足条件的多重集合A：{1,1,2}。
  • 对于k=4，不存在满足条件的多重集合A。

样例输入2

7 7

样例输出2

1
3
4
3
2
1
1

Source/Category

加入题单

算法标签：