103157: [Atcoder]ABC315 Ex - Typical Convolution Problem
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Score : $650$ points
Problem Statement
You are given a sequence $(A_1, A_2, \ldots , A_N)$. Let us define a sequence $(F_0, F_1, \ldots , F_N)$ by the following formulae.
- $F_0 = 1$
- $F_n = A_n\displaystyle\sum_{i+j<n}F_iF_j$ $(1 \leq n \leq N)$
Find $F_1, \ldots , F_N$ modulo $998244353$.
Constraints
- $1 \leq N \leq 2 \times 10^5$
- $0 \leq A_i < 998244353$
- All input values are integers.
Input
The input is given from Standard Input in the following format:
$N$ $A_1$ $A_2$ $\ldots$ $A_N$
Output
Print $F_1, \ldots , F_N$ modulo $998244353$ in this order, with spaces in between.
Sample Input 1
5 1 2 3 4 5
Sample Output 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$. Similarly, we find $F_3 = 48, F_4 = 496, F_5 = 6240$.
Sample Input 2
3 12345 678901 2345678
Sample Output 2
12345 790834943 85679169
Input
Output
得分：$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