【模板】多项式乘法(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 page.problem_detail.sidebar.show_category
- Tags
- (無)
- 遞交數
- 10
- 已通過
- 2
- 通過率
- 20%
- 上傳者
-
XKM
相關
在下列訓練計劃中: