← 返回题目列表

AtCoder · abc230_h

H. 金条

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

高桥赢得了夹娃娃机比赛并获得了“无限量”金块。
称重块的数量不受限制 w_1, w_2, \dots, w_K 每公斤,且称重的袋子数量不受限制 1 每公斤塞满它们。

高桥可以带回家一个非空包。
一个袋子可以包含零个或多个其他非空袋子以及零个或多个金块。

安排一辆载重量为 W 公斤,他对装金块并带回家一个重的袋子的方法很感兴趣 w 公斤总计 w = 2, 3, \dots, W.
求模数 998244353,每个包的可能状态 w = 2, 3, \dots, W。在这里,

  • 当两个金块的重量相同时,称它们是相同的;
  • 当元素为袋子和两个袋子中的金块的两个多重集相同时,称两个袋子处于相同状态。

约束

  • 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 \to w_i \neq w_j (1 \leq i,j \leq K)
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

W K
w_1 w_2 \dots w_K

输出

打印答案 W - 1 行。
的 i- 第行应包含计数 w = i + 1.


样本输入 1

4 1
1

示例输出 1

1
2
4

下图列举了包的可能状态 w = 2, 3, 4。 (圆圈代表一个袋子。)

image


示例输入 2

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

示例输出 2

1
3
7
18
45
121
325
904
2546