luogu#P3803. 【模板】多项式乘法(FFT)

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

题目背景

这是一道多项式乘法模板题。

注意:本题并不属于中国计算机学会划定的提高组知识点考察范围。

题目描述

给定一个 nn 次多项式 F(x)F(x),和一个 mm 次多项式 G(x)G(x)

请求出 F(x)F(x)G(x)G(x) 的卷积。

输入格式

第一行两个整数 n,mn,m

接下来一行 n+1n+1 个数字,从低到高表示 F(x)F(x) 的系数。

接下来一行 m+1m+1 个数字,从低到高表示 G(x)G(x) 的系数。

输出格式

一行 n+m+1n+m+1 个数字,从低到高表示 F(x)G(x)F(x) \cdot G(x) 的系数。

1 2
1 2
1 2 1
1 4 5 2

提示

保证输入中的系数大于等于 00 且小于等于 99

对于 100%100\% 的数据:1n,m1061 \le n, m \leq {10}^6