AT_arc145_f [ARC145F] Modulo Sum of Increasing Sequences

题目描述

请你求出满足以下条件的长度为 $N$ 的广义单调递增序列 $A=(A_1,A_2,\ldots,A_N)$ 的个数，并对 $998244353$ 取模，分别输出每个 $K=0,1,\ldots,\mathrm{MOD}-1$ 时的答案。

• $A$ 的每个元素都是 $0$ 到 $M$ 之间的整数。
• $A$ 的所有元素之和除以 $\mathrm{MOD}$ 的余数等于 $K$。

广义单调递增序列指的是，对于一个序列 $B$，若其长度为 $|B|$，对于所有 $1\leq i\leq |B|-1$，都有 $B_i\leq B_{i+1}$，则 $B$ 是广义单调递增序列。

输入格式

输入一行，包含三个整数：

$N$ $M$ $\mathrm{MOD}$

输出格式

请输出 $\mathrm{MOD}$ 行。第 $K$ 行（$K=0,1,\ldots,\mathrm{MOD}-1$）输出满足条件且元素和模 $\mathrm{MOD}$ 等于 $K$ 的广义单调递增序列的个数，对 $998244353$ 取模。

样例 1

输入

2 2 4

输出

2 1 2 1

样例 2

输入

3 45 3

输出

5776 5760 5760

样例 3

输入

1000000 1000000 6

输出

340418986 783857865 191848859 783857865 340418986 635287738

说明/提示

数据范围

• $1\leq N,M\leq 10^6$
• $1\leq \mathrm{MOD}\leq 500$
• 输入均为整数

样例解释 1

所有由 $0$ 到 $2$ 之间的整数构成的长度为 $2$ 的广义单调递增序列有 $6$ 种，分别为 $(0,0),(0,1),(0,2),(1,1),(1,2),(2,2)$。

• 元素和模 $4$ 等于 $0$ 的有 $2$ 种：$(0,0),(2,2)$
• 元素和模 $4$ 等于 $1$ 的有 $1$ 种：$(0,1)$
• 元素和模 $4$ 等于 $2$ 的有 $2$ 种：$(0,2),(1,1)$
• 元素和模 $4$ 等于 $3$ 的有 $1$ 种：$(1,2)$

题目描述

请输出对 $998244353$ 取模的答案。

由 ChatGPT 4.1 翻译