【模板】多项式乘法(FFT/NTT)

【模板】多项式乘法(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\)。

来源

信息

ID
1055
难度
9
分类
FFT 点击显示
标签
(无)
递交数
10
已通过
2
通过率
20%
上传者

相关

在下列训练计划中:

模板 | Templates