Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 1200 点
問題文
0 以上 M 以下の整数からなる長さ N の広義単調増加列 A=(A_1,A_2,\ldots,A_N) のうち、以下を満たすものの個数を 998244353 で割ったあまりを各 K=0,1,\ldots,\mathrm{MOD}-1 に対して求めてください。
- A の要素の総和を \mathrm{MOD} で割ったあまりが K に等しい。
広義単調増加列とは
ある数列 B について、 B の長さを |B| としたとき、全ての整数 i (1 \le i \le |B| - 1) について、 B_i \leq B_{i+1} が成り立つとき、またそのときに限って、 B は広義単調増加列です。制約
- 1 \leq N ,M\leq 10^6
- 1\leq \mathrm{MOD}\leq 500
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M \mathrm{MOD}
出力
各 K=0,1,\ldots,\mathrm{MOD}-1 に対して、条件を満たす数列の個数を 998244353 で割ったあまりを出力せよ。
入力例 1
2 2 4
出力例 1
2 1 2 1
0 以上 2 以下の整数からなる長さ 2 の広義単調増加列は (0, 0), (0, 1),(0,2), (1,1),(1,2),(2,2) の 6 通りです。
-
総和を 4 で割ったあまりが 0 のもの:(0,0),(2,2) の 2 通り
-
総和を 4 で割ったあまりが 1 のもの:(0,1) の 1 通り
-
総和を 4 で割ったあまりが 2 のもの:(0,2),(1,1) の 2 通り
-
総和を 4 で割ったあまりが 3 のもの:(1,2) の 1 通り
です。
入力例 2
3 45 3
出力例 2
5776 5760 5760
入力例 3
1000000 1000000 6
出力例 3
340418986 783857865 191848859 783857865 340418986 635287738
998244353 で割ったあまりを答えてください。
Score : 1200 points
Problem Statement
Find the number, modulo 998244353, of non-decreasing sequences A=(A_1,A_2,\ldots,A_N) of length N consisting of integers between 0 and M (inclusive) that satisfy the following, for each K=0,1,\ldots,\mathrm{MOD}-1:
- the sum of the elements in A is congruent to K modulo \mathrm{MOD}.
What is a non-decreasing sequence?
A sequence B is non-decreasing if and only if B_i \leq B_{i+1} for every integer (1 \le i \le |B| - 1), where |B| is the length of B.Constraints
- 1 \leq N ,M\leq 10^6
- 1\leq \mathrm{MOD}\leq 500
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M \mathrm{MOD}
Output
For each K=0,1,\ldots,\mathrm{MOD}-1, print the number, modulo 998244353, of sequences that satisfy the condition.
Sample Input 1
2 2 4
Sample Output 1
2 1 2 1
There are 6 non-decreasing sequences of length 2 consisting of integers between 0 and 2: (0, 0), (0, 1),(0,2), (1,1),(1,2),(2,2). Here, we have:
-
2 sequences whose sums are congruent to 0 modulo 4: (0,0),(2,2);
-
1 sequence whose sum is congruent to 1 modulo 4: (0,1);
-
2 sequences whose sums are congruent to 2 modulo 4: (0,2),(1,1);
-
1 sequence whose sum is congruent to 3 modulo 4: (1,2).
Sample Input 2
3 45 3
Sample Output 2
5776 5760 5760
Sample Input 3
1000000 1000000 6
Sample Output 3
340418986 783857865 191848859 783857865 340418986 635287738
Print the counts modulo 998244353.