201455: [AtCoder]ARC145 F - Modulo Sum of Increasing Sequences
Description
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$.