【模板】多项式乘法(FFT/NTT)
题目描述
输入两个多项式,输出这两个多项式的乘积。
输入输出格式
输入格式
第一行两个整数 \(n\) 和 \(m\),分别表示两个多项式的次数。
第二行 \(n + 1\) 个整数,分别表示第一个多项式的 \(0\) 到 \(n\) 次项前的系数。
第三行 \(m + 1\) 个整数,分别表示第二个多项式的 \(0\) 到 \(m\) 次项前的系数。
输出格式
一行 \(n + m + 1\) 个整数,分别表示乘起来后的多项式的 \(0\) 到 \(n + m\) 次项前的系数。
样例
输入
1 2
1 2
1 2 1
输出
1 4 5 2
数据范围
\(0 \leq n, m \leq 10 ^ 5\),保证输入中的系数大于等于\( 0 \)且小于等于 \(9\)。
来源
相关
在下列训练计划中: