You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[ABC315Ex] Typical Convolution Problem

题面翻译

题目描述

给定一个长为 $n$ 的序列 $a$，按如下方法计算 $f(x)$：

• $f(0)=1$;
• 当整数 $m\in[1,n]$ 时，$f(m)=a_m\times (\displaystyle\sum_{i+j\lt m} f(i)\times f(j))$。

对于每个整数 $i\in[1,n]$，计算 $f(i)$ $\bmod$ $998244353$ 的值。

输入格式

第一行为序列长度 $n$，第二行输入 $n$ 个整数表示序列 $a$。

输出格式

依次输出 $f(1)$，$f(2)$，…，$f(n)$ 对 $998244353$ 取模后的值，相邻两个数之间以单个空格隔开。

说明/提示

数据规模与约定

$1\le n\le 2\times 10^5$，$a_i\in[0,998244352]$。

样例 #1

样例输入 #1

5
1 2 3 4 5

样例输出 #1

1 6 48 496 6240

样例 #2

样例输入 #2

3
12345 678901 2345678

样例输出 #2

12345 790834943 85679169

样例解释1

$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$ 。