Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
高橋君は、互いに区別できない K 面サイコロを N 個振ります。なお、K 面サイコロとは、1 以上 K 以下のすべての整数の目の出る可能性のあるサイコロのことを指します。 各 i=2,3,...,2K に対し、以下の値を 998244353 で割ったあまりをそれぞれ求めてください。
- どの異なる 2 つのサイコロの出目の和も i にならないような出目の組の場合の数
なお、サイコロ同士は区別しないことに注意してください。したがって、2 つの出目の組が異なるとは、ある目 k が存在し、出目 k の個数が異なることを指します。
制約
- 1 \leq K \leq 2000
- 2 \leq N \leq 2000
- K,N は整数である
入力
入力は以下の形式で標準入力から与えられる。
K N
出力
2K-1 個の整数を出力せよ。t(1\leq t\leq 2K-1) 個目には、i=t+1 のときの答えを出力せよ。
入力例 1
3 3
出力例 1
7 7 4 7 7
- i=2 のとき、出目の組 (1,2,2),(1,2,3),(1,3,3),(2,2,2),(2,2,3),(2,3,3),(3,3,3) が条件を満たすので、このときの答えは 7 です。
- i=3 のとき、出目の組 (1,1,1),(1,1,3),(1,3,3),(2,2,2),(2,2,3),(2,3,3),(3,3,3) が条件を満たすので、このときの答えは 7 です。
- i=4 のとき、出目の組 (1,1,1),(1,1,2),(2,3,3),(3,3,3) が条件を満たすので、このときの答えは 4 です。
入力例 2
4 5
出力例 2
36 36 20 20 20 36 36
入力例 3
6 1000
出力例 3
149393349 149393349 668669001 668669001 4000002 4000002 4000002 668669001 668669001 149393349 149393349
Score : 700 points
Problem Statement
Takahashi throws N dice, each having K sides with all integers from 1 to K. The dice are NOT pairwise distinguishable. For each i=2,3,...,2K, find the following value modulo 998244353:
- The number of combinations of N sides shown by the dice such that the sum of no two different sides is i.
Note that the dice are NOT distinguishable, that is, two combinations are considered different when there exists an integer k such that the number of dice showing k is different in those two.
Constraints
- 1 \leq K \leq 2000
- 2 \leq N \leq 2000
- K and N are integers.
Input
Input is given from Standard Input in the following format:
K N
Output
Print 2K-1 integers. The t-th of them (1\leq t\leq 2K-1) should be the answer for i=t+1.
Sample Input 1
3 3
Sample Output 1
7 7 4 7 7
- For i=2, the combinations (1,2,2),(1,2,3),(1,3,3),(2,2,2),(2,2,3),(2,3,3),(3,3,3) satisfy the condition, so the answer is 7.
- For i=3, the combinations (1,1,1),(1,1,3),(1,3,3),(2,2,2),(2,2,3),(2,3,3),(3,3,3) satisfy the condition, so the answer is 7.
- For i=4, the combinations (1,1,1),(1,1,2),(2,3,3),(3,3,3) satisfy the condition, so the answer is 4.
Sample Input 2
4 5
Sample Output 2
36 36 20 20 20 36 36
Sample Input 3
6 1000
Sample Output 3
149393349 149393349 668669001 668669001 4000002 4000002 4000002 668669001 668669001 149393349 149393349