/ 
Time Limit: 8 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
クレーンゲームの大会で優勝した高橋君は金塊詰め放題の権利を得ました。
会場には w_1 \lbrack\mathrm{kg}\rbrack, w_2 \lbrack\mathrm{kg}\rbrack, \dots, w_K \lbrack\mathrm{kg}\rbrack の重さの金塊、および金塊を詰める 1 \lbrack\mathrm{kg}\rbrack の袋が無尽蔵にあります。
高橋君は 1 個の空でない袋を持ち帰ることができます。
袋には 0 個以上の空でない袋と 0 個以上の金塊を入れることができます。
耐荷重量 W \lbrack\mathrm{kg}\rbrack のトラックを手配した高橋君は、 w = 2, 3, \dots, W について持ち帰る袋の総重量が w \lbrack\mathrm{kg}\rbrack である詰め方としてあり得る状態の数が気になりました。
w = 2, 3, \dots, W について状態数を 998244353 で割ったあまりを求めてください。ただし、
- 2 つの金塊が同じであるとは、金塊の重さが同じであることをいいます。
- 2 つの袋が同じ状態であるとは、袋に入っている袋および金塊からなる多重集合が一致することをいいます。
制約
- 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
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