Score : $600$ points

问题描述

高桥在一场夹娃娃机比赛中获胜，并获得“任意装满”金砖的奖励。 有无限数量的金砖，每块分别重 $w_1, w_2, \dots, w_K$ 千克，以及无限数量的袋子，每个袋子重 $1$ 千克用来装这些金砖。

高桥可以带走一个非空的袋子。 一个袋子中可以包含任意数量的其他非空袋子和任意数量的金砖。

在安排好一辆装载能力为 $W$ 千克的卡车后，他对将金砖装入袋中并带走总重为 $w = 2, 3, \dots, W$ 千克的袋子的方法数产生了兴趣。 对于每个 $w = 2, 3, \dots, W$，请计算满足条件的袋子状态的可能性数量，结果对 $998244353$ 取模。

这里，

• 当两块金砖的重量相同时，认为它们是相同的；
• 当两个袋子中的元素（包括袋子本身和其中的金砖）构成的多重集合相同时，认为这两个袋子处于相同的状态。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

Takahashi won a claw machine competition and was awarded "all-you-can-stuff" gold blocks.
There are unlimited numbers of blocks weighing $w_1, w_2, \dots, w_K$ kilograms each, and an unlimited number of bags weighing $1$ kilogram each to stuff them.

Takahashi can bring home one non-empty bag.
A bag can contain zero or more other non-empty bags and zero or more gold blocks.

After arranging a truck with a load capacity of $W$ kilograms, he gets interested in the number of ways to stuff gold blocks and bring home a bag that weighs $w$ kilograms in total for $w = 2, 3, \dots, W$.
Find the number, modulo $998244353$, of possible states of the bag for each $w = 2, 3, \dots, W$. Here,

• two gold blocks are said to be the same when their weights are the same;
• two bags are said to be in the same state when the two multisets whose elements are the bags and gold blocks in the two bags are the same.

Constraints

• $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)$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$W$ $K$

$w_1$ $w_2$ $\dots$ $w_K$

Output

Print the answer in $W - 1$ lines.
The $i$-th line should contain the count for $w = i + 1$.

Sample Input 1

4 1
1

Sample Output 1

1
2
4

The figure below enumerates the possible states of the bag for $w = 2, 3, 4$. (A circle represents a bag.)

Sample Input 2

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

Sample Output 2

1
3
7
18
45
121
325
904
2546

update @ 2024/3/10 10:04:18