/ 
Time Limit: 5 sec / Memory Limit: 1024 MB
配点 : 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
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