#P18842. [Croatian CPC2021] Idilična ivica

[Croatian CPC2021] Idilična ivica

Idilična ivica

题目描述

Malnar 的花园里有一道由 nn 株植物依次排列组成的篱笆,第 ii 株植物的高度为 AiA_i,所有植物的总高度为 SS。

他打算修剪这些植物。每株植物最多只能被剪一次。修剪时,可以在某个非负整数高度 vv 将一株高于 vv 的植物剪到高度 vv。但他不太擅长使用剪刀:如果在高度 vv 修剪某株植物,就必须把与它相邻且严格高于 vv 的植物也剪到高度 vv。被一起修剪的植物同样遵守这一规则。

不必修剪所有植物,也可以完全不修剪。

修剪示意图

左图是合法的修剪方式,右图是不合法的修剪方式;右图在第 22、33 株之间以及第 44、55 株之间的修剪不符合规则。

对于每个 X=0,1,…,SX=0,1,\ldots,S,求最终总高度恰好为 XX 的不同篱笆数量。只要至少一株植物的最终高度不同,就认为两道篱笆不同。答案对 998244353998244353 取模。

输入格式

第一行包含一个整数 nn。

第二行包含 nn 个整数 A1,A2,…,AnA_1,A_2,\ldots,A_n。

输出格式

输出 S+1S+1 行。第 ii 行输出总高度为 i−1i-1 的不同篱笆数量对 998244353998244353 取模后的结果。

数据范围

  • 1≤n≤20001\le n\le2000;
  • 0≤Ai≤20000\le A_i\le2000;
  • S=∑i=1nAi≤2000S=\sum_{i=1}^n A_i\le2000。

样例 1

输入

4
0 0 1 6

输出

1
0
1
1
1
1
1
1

样例 2

输入

3
4 6 0

输出

1
0
1
0
1
0
1
0
1
1
1

样例 3

输入

5
1 1 2 1 0

输出

1
0
0
0
1
1

样例 1 解释

无法使总高度为 11:如果将第 33 株剪到高度 00,第 44 株也必须剪到高度 00;反过来也是如此。

对于 22 到 66 中的每个总高度,恰好有一种方式,即只修剪第 44 株。总高度 77 对应完全不修剪。将所有植物剪到高度 00,可以得到总高度为 00 的篱笆。