/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 1100 点
問題文
長さ N+1 の非負整数列 X=(X_1,X_2,\ldots,X_{N+1}) が与えられます．ただし，X_{N+1}=0 です．
あなたは，以下の操作を行うことができます．
- 1 \leq i \leq N かつ X_i \geq 1 を満たす整数 i を選び，X_i から 1 を引き，X_{i+1} に 2 を足す．
整数 K が与えられます．各 k=1,2,\ldots,K について，与えられた数列に操作をちょうど k 回行った結果としてありうる数列の個数を 998244353 で割った余りを求めてください．
制約
- 1 \leq N \leq 20
- 1 \leq K \leq 250000
- 0 \leq X_i \leq 250000 (1 \leq i \leq N)
- X_{N+1}=0
- 入力はすべて整数である．
入力
入力は以下の形式で標準入力から与えられる．X_{N+1} は入力に含まれない．
N K X_1 X_2 \ldots X_N
出力
k=1,2,\cdots,K に対する答えをこの順に，空白区切りで 1 行に出力せよ．
入力例 1
2 5 1 1
出力例 1
2 1 1 1 0
操作を 1 回行った結果としてありうる数列は (0,3,0) と (1,0,2) の 2 個です． 操作を 2 回行った結果としてありうる数列は (0,2,2) の 1 個です．この数列を得る操作の順序は複数ありますが，数列の個数としては 1 個と数えます．
入力例 2
2 4 1 0
出力例 2
1 1 1 0
初めの数列は (1,0,0) です．操作を行うごとに，数列は (0,2,0)，(0,1,2)，(0,0,4) と変化します．操作を 4 回行うことはできません．
入力例 3
1 1 0
出力例 3
0
入力例 4
3 4 0 0 2
出力例 4
1 1 0 0
入力例 5
4 7 1 0 1 0
出力例 5
2 3 4 4 5 5 5
Score : 1100 points
Problem Statement
You are given a sequence of non-negative integers of length N+1, X=(X_1,X_2,\ldots,X_{N+1}), where X_{N+1}=0.
You can perform the following operation.
- Choose an integer i satisfying 1 \leq i \leq N and X_i \geq 1, subtract 1 from X_i, and add 2 to X_{i+1}.
You are given an integer K. For each k=1,2,\ldots,K, find the number, modulo 998244353, of sequences that can result from performing the operation exactly k times on the given sequence.
Constraints
- 1 \leq N \leq 20
- 1 \leq K \leq 250000
- 0 \leq X_i \leq 250000 (1 \leq i \leq N)
- X_{N+1}=0
- All input values are integers.
Input
The input is given from Standard Input in the following format. X_{N+1} is not included in the input.
N K X_1 X_2 \ldots X_N
Output
Output the answers for k=1,2,\cdots,K in this order, separated by spaces, on a single line.
Sample Input 1
2 5 1 1
Sample Output 1
2 1 1 1 0
The sequences that can result from performing the operation once are (0,3,0) and (1,0,2), so there are two of them. The only sequence that can result from performing the operation twice is (0,2,2), so there is one. Multiple orders of operations yield this sequence, but it is counted as one sequence.
Sample Input 2
2 4 1 0
Sample Output 2
1 1 1 0
The initial sequence is (1,0,0). With each operation, the sequence changes to (0,2,0), (0,1,2), (0,0,4). The operation cannot be performed four times.
Sample Input 3
1 1 0
Sample Output 3
0
Sample Input 4
3 4 0 0 2
Sample Output 4
1 1 0 0
Sample Input 5
4 7 1 0 1 0
Sample Output 5
2 3 4 4 5 5 5