← 返回题目列表

AtCoder · abc315_h

Ex. 典型的卷积问题

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

分数: 650 点

问题陈述

给你一个序列 (A_1, A_2, \ldots , A_N)。 让我们定义一个序列 (F_0, F_1, \ldots , F_N) 由以下公式计算。

  • F_0 = 1
  • F_n = A_n\displaystyle\sum_{i+j<n}F_iF_j (1 \leq n \leq N)

查找 F_1, \ldots , F_N 模数 998244353.

约束

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq A_i < 998244353
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \ldots A_N

输出

打印 F_1, \ldots , F_N 模数 998244353 按此顺序,中间有空格。


示例输入 1

5
1 2 3 4 5

示例输出 1

1 6 48 496 6240

F_1 = A_1F_0F_0 = 1. F_2 = A_2(F_0F_0+F_0F_1+F_1F_0) = 6。 同样,我们发现 F_3 = 48, F_4 = 496, F_5 = 6240.


示例输入 2

3
12345 678901 2345678

示例输出 2

12345 790834943 85679169