1054: 【模板题】分治 FFT
[Creator : ]
Description
# 题目背景
也可用多项式求逆解决。
# 题目描述
给定序列 $g_{1\dots n - 1}$,求序列 $f_{0\dots n - 1}$。
其中 $f_i=\sum_{j=1}^if_{i-j}g_j$,边界为 $f_0=1$。
答案对 $998244353$ 取模。
也可用多项式求逆解决。
# 题目描述
给定序列 $g_{1\dots n - 1}$,求序列 $f_{0\dots n - 1}$。
其中 $f_i=\sum_{j=1}^if_{i-j}g_j$,边界为 $f_0=1$。
答案对 $998244353$ 取模。
Input
第一行一个整数 $n$ 。
第二行 $n-1$ 个整数 $g_{1\dots n - 1}$。
第二行 $n-1$ 个整数 $g_{1\dots n - 1}$。
Output
一行 $n$ 个整数,表示 $f_{0\dots n - 1}$ 对 $998244353$ 取模后的值。
Constraints
$2\leq n\leq 10^5$,$0\leq g_i<998244353$。
Sample 1 Input
4
3 1 2
Sample 1 Output
1 3 10 35
Sample 2 Input
10
2 456 32 13524543 998244352 0 1231 634544 51
Sample 2 Output
1 2 460 1864 13738095 55389979 617768468 234028967 673827961 708520894