AT_abc230_h [ABC230H] Bullion

题目描述

在抓娃娃机比赛中获胜的高桥君获得了随意装金块的权利。
会场里有重量分别为 $w_1\ [\mathrm{kg}],\ w_2\ [\mathrm{kg}],\ \dots,\ w_K\ [\mathrm{kg}]$ 的金块，以及无限多的 $1\ [\mathrm{kg}]$ 的袋子可供使用。

高桥君可以带回 $1$ 个非空的袋子。
袋子里可以放入 $0$ 个或多个非空的袋子和 $0$ 个或多个金块。

高桥君准备了一辆最大承重为 $W\ [\mathrm{kg}]$ 的卡车，他想知道对于 $w=2,3,\dots,W$，能够带回总重量为 $w\ [\mathrm{kg}]$ 的袋子的不同装法有多少种。
请对于 $w=2,3,\dots,W$，输出状态数对 $998244353$ 取模的结果。需要注意：

• 两个金块被认为相同，当且仅当它们的重量相同。
• 两个袋子被认为状态相同，当且仅当它们内部包含的袋子和金块组成的多重集合完全一致。

输入格式

输入以如下格式从标准输入读入。

$W$ $K$ $w_1$ $w_2$ $\dots$ $w_K$

输出格式

请输出 $W-1$ 行。
第 $i$ 行输出 $w=i+1$ 时的答案。

输入输出样例 #1

输入 #1

4 1
1

输出 #1

1
2
4

输入输出样例 #2

输入 #2

10 10
1 2 3 4 5 6 7 8 9 10

输出 #2

1
3
7
18
45
121
325
904
2546

说明/提示

约束条件

• $2 \leq W \leq 2.5 \times 10^5$
• $1 \leq K \leq W$
• $1 \leq w_i \leq W$ $(1 \leq i \leq K)$
• $i \neq j \implies w_i \neq w_j$ $(1 \leq i,j \leq K)$
• 所有输入均为整数。

样例解释 1

对于 $w=2,3,4$，所有可能的袋子状态如下图所示（圆形线条表示袋子）。

由 ChatGPT 4.1 翻译