102307: [AtCoder]ABC230 H - Bullion
Description
Score : $600$ points
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
Input
题意翻译
首先你得到了一个重量参数 $W$。 现在有 $K$ 种金块，每种金块的重量分别是 $w_i$，保证其各不相同。每种金块数量无限，同时还有无限个重量为 $1$，容积无限的袋子。 每个袋子中可以装大于 $0$ 个金块和大于 $0$ 个非空的袋子。注意袋子不能是空的。 你想知道，当一个袋子的重量**恰好**为 $2,3,\dots,W$ 时，其中装金块的情况有多少种。对于每个答案输出一行，答案对 $998244353$ 取模。 注意，相同质量的金块之间没有差别，袋子之间也没有差别。Output
得分：$600$分
问题描述
高桥在抓娃娃机比赛中获胜，并获得了“随心所欲”黄金块的奖励。
有无限数量的每个重$w_1, w_2, \dots, w_K$千克的黄金块，以及无限数量的每个重$1$千克的袋子用来装它们。
高桥可以带回一个非空的袋子。
一个袋子可以包含零个或多个其他非空的袋子，以及零个或多个黄金块。
在安排了一个载重为$W$千克的卡车后，他对将黄金块装入袋子并带回家一个总重为$w$千克的袋子的方法数产生了兴趣，其中$w = 2, 3, \dots, W$。
对于每个$w = 2, 3, \dots, W$，找出袋子状态的可能性数，取模$998244353$。这里，
- 当两个黄金块的重量相同时，称这两个黄金块是相同的；
- 当两个袋子中包含的袋子和黄金块的多集相同时，称这两个袋子处于相同的状态。
约束条件
- $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$时袋子的可能状态。（圆圈表示一个袋子。）
样例输入 2
10 10 1 2 3 4 5 6 7 8 9 10
样例输出 2
1 3 7 18 45 121 325 904 2546