#P13479. [ABC315Ex] Typical Convolution Problem

    ID: 12663 传统题 5000ms 1024MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2500省选/NOI-卷积转化一维前缀和CDQ 分治分治 FFTNTT

[ABC315Ex] Typical Convolution Problem

AT_abc315_h [ABC315Ex] Typical Convolution Problem

5s,1g

题目描述

给定一个长为 nn 的序列 aa,按如下方法计算 f(x)f(x):

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

对于每个整数 i∈[1,n]i\in[1,n],计算 f(i)f(i)  mod \bmod 998244353998244353 的值。

输入格式

第一行为序列长度 nn,第二行输入 nn 个整数表示序列 aa。

输出格式

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

输入输出样例 #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≤n≤2×1051\le n\le 2\times 10^5,ai∈[0,998244352]a_i\in[0,998244352]。