← 返回题目列表

AtCoder · wtf22_day2_d

D. 猫跳

中文机器翻译题面 查看原题

分数: 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