D - Cat Jumps

Contest Duration: 2023-09-09 13:00:00+0900 - 2023-09-09 18:00:00+0900 (local time) (300 minutes) Back to Home

D - Cat Jumps Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 2000 点

問題文

正整数列 A_1,A_2,\cdots,A_N が与えられます． S=N+\sum_{1 \leq i \leq N}A_i と定義します．

猫のすぬけくんは S 枚のカードを持っています．各カードには整数が書かれており，それらは A_1,A_2,\cdots,A_N,-1,\cdots,-1 です．特に，-1 のカードは \sum_{1 \leq i \leq N}A_i 枚あります．

すぬけくんは今，数直線上の座標 0 の位置に立っています．すぬけくんはこれから S 回，以下の操作を行います．

現在すぬけくんがいる座標を x とする．持っているカードを 1 枚選んで捨てる．捨てたカードに書いてあった数を v とするとき，座標 x+v へとジャンプする．ジャンプ後の座標が 0 なら，コインを 1 枚獲得する．

各 k=1,2,\cdots,N に対して，すぬけくんがちょうど k 枚のコインを獲得するようなジャンプの列が何通りあるかを 998244353 で割ったあまりを求めてください．

数えるのがジャンプの列であることに注意してください．つまり，2 つのカードに書いてある数が同じ場合，それらを捨てる操作は同一視します．

制約

1 \leq N \leq 5000
1 \leq A_i \leq 5000
入力される値はすべて整数．

入力

入力は以下の形式で標準入力から与えられる．

N
A_1 A_2 \cdots A_N

出力

N 行出力せよ． i 行目には k=i に対する答えを出力せよ．

入力例 1

2
1 1

出力例 1

2
4

例えば，(-1,+1,+1,-1) というジャンプの列が考えられます．この場合，すぬけくんの座標は 0 \to -1 \to 0 \to 1 \to 0 と変化し，2 枚のコインを獲得します．

以下に，すべてのジャンプの列とその結果獲得するコインの枚数を示します．

(-1,-1,+1,+1): 1 枚
(-1,+1,-1,+1): 2 枚
(-1,+1,+1,-1): 2 枚
(+1,-1,-1,+1): 2 枚
(+1,-1,+1,-1): 2 枚
(+1,+1,-1,-1): 1 枚

入力例 2

3
1 2 3

出力例 2

140
220
144

入力例 3

20
16 6 15 19 1 9 6 1 11 7 6 12 3 11 11 18 10 9 15 5

出力例 3

Score : 2000 points

Problem Statement

You are given a sequence of positive integers A_1,A_2,\cdots,A_N. Let S=N+\sum_{1 \leq i \leq N}A_i.

Cat Snuke has S cards. Each card has an integer written on it. The integers on the cards are A_1,A_2,\cdots,A_N,-1,\cdots,-1. Particularly, there are \sum_{1 \leq i \leq N}A_i cards with -1.

Snuke is now standing at the coordinate 0 on a number line. He will perform the following operation S times.

Let x be the current coordinate of Snuke. Choose and discard one of the cards he has. Let v be the number on the discarded card, and jump to the coordinate x+v. If he has jumped to the coordinate 0, earn one coin.

For each k=1,2,\cdots,N, find the number, modulo 998244353, of sequences of moves for Snuke such that he earns exactly k coins.

Note that you should count sequences of moves. Namely, if two cards have the same number, discarding one of them is not distinguished from discarding the other.

Constraints

1 \leq N \leq 5000
1 \leq A_i \leq 5000
All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print N lines. The i-th line should contain the answer for k=i.

Sample Input 1

2
1 1

Sample Output 1

2
4

One possible sequence of moves is (-1,+1,+1,-1). Here, Snuke changes his coordinate as 0 \to -1 \to 0 \to 1 \to 0 and earns two coins.

Here are all possible sequences of moves and the number of coins that will be earned.

(-1,-1,+1,+1): one coin
(-1,+1,-1,+1): two coins
(-1,+1,+1,-1): two coins
(+1,-1,-1,+1): two coins
(+1,-1,+1,-1): two coins
(+1,+1,-1,-1): one coin

Sample Input 2

3
1 2 3

Sample Output 2

140
220
144

Sample Input 3

20
16 6 15 19 1 9 6 1 11 7 6 12 3 11 11 18 10 9 15 5

Sample Output 3