#P5373. 【模板】多项式复合函数

    ID: 4299 远端评测题 4000ms 500MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>快速傅里叶变换,FFT快速数论变换 NTT数论数学O2优化

【模板】多项式复合函数

题目背景

有一天,NaCly_Fish看见 rqy\mathsf r \color{red} \mathsf{qy} 在群里说:“终于把多项式复合写完啦!qwq”
她便好奇地去问 rqy\mathsf r \color{red} \mathsf{qy}:“这个东西怎么写啊?”

rqy\mathsf r \color{red} \mathsf{qy} 只丢给了她一份嘤文的 pdf,然而她根本看不懂。
于是她求助于你,希望你能帮她解决这个难题。

题目描述

给定一个 nn 次多项式 F(x)F(x),和一个 mm 次多项式 G(x)G(x),你需要求一个 nn 次多项式 H(x)H(x) ,满足条件:

H(x)F(G(x)) (mod xn+1)H(x) \equiv F(G(x))\space (\text{mod }x^{n+1})

换种说法,你要求的多项式应满足:

$$H(x) \equiv \sum\limits_{i=0}^n [x^i]F(x)\times G(x)^i \space (\text{mod }x^{n+1}) $$

将结果的各项系数对 998244353998244353 取模。

输入格式

第一行两个正整数 n,mn,m ,分别表示 F(x)F(x)G(x)G(x) 的次数
第二行 n+1n+1 个非负整数 fif_i,表示 F(x)F(x)ii 次项系数
第三行 m+1m+1 个非负整数 gig_i,表示 G(x)G(x)ii 次项系数

输出格式

输出一行 n+1n+1 个非负整数,从低到高表示 H(x)H(x) 的系数

5 1
1 9 2 6 0 8
1 7

26 497 4900 29498 96040 134456 

提示

数据范围:
1mn200001\le m \le n \le 20000
fi,gi[0,998244353)Zf_i,g_i \in [0,998244353)\cap \mathbb Z