分数: 2000 点
问题陈述
给你一个正整数序列 A_1,A_2,\cdots,A_N。 让 S=N+\sum_{1 \leq i \leq N}A_i.
猫 Snuke 有 S 张卡片。 每张卡片上都写有一个整数。这些卡片上的整数是 A_1,A_2,\cdots,A_N,-1,\cdots,-1。 特别地,有 \sum_{1 \leq i \leq N}A_i 卡片 上面写着 -1.
Snuke 现在站在数轴上的坐标 0 。 他将执行以下操作 S 次。
- 让 x 为 Snuke 当前的坐标。 选择并丢弃他拥有的一张卡片。 记 v 为被丢弃的卡片上的数字,然后跳到坐标 x+v。 如果他跳到了坐标 0,获得一个硬币。
对于每个 k=1,2,\cdots,N,求模数 998244353,Snuke 的移动序列,使他恰好获得 k 硬币。
。请注意,你应该计算移动序列。 也就是说,如果两张卡片的数字相同,丢弃其中一张与丢弃另一张没有区别。
约束
- 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)。 在这里,Snuke 的坐标变化为 0 \to -1 \to 0 \to 1 \to 0 并获得两个硬币。
这是所有可能的移动序列以及将获得的硬币数量。
- (-1,-1,+1,+1):一个硬币
- (-1,+1,-1,+1):两个硬币
- (-1,+1,+1,-1):两个硬币
- (+1,-1,-1,+1):两个硬币
- (+1,-1,+1,-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
507808441 401798892 110460932 680359166 737048635 442374434 737773176 980506765 473506608 693729211 532774651 621434128 4273369 839437048 585784927 590354055 969740008 825216624 442091194 660636013