https://www.luogu.org/problem/show?pid=3803

题目背景

这是一道模版题

题目描述

给定一个n次多项式F(x)，和一个m次多项式G(x)。

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

输入输出格式

输入格式：

第一行2个正整数n,m。

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

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

输出格式：

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

输入输出样例

1 21 21 2 1

1 4 5 2

说明

保证输入中的系数大于等于 0 且小于等于9。

总共14组测试数据。

对于第1-4组数据：n<=5000,m<=5000,20pts，0.5s。

对于第5-10组数据：n<=300000,m<=300000,60pts，1s。

对于第11-14组数据：n<=1000000,m<=1000000,20pts，2s。

数据有一定梯度。

空间限制：256MB

【模版】多项式乘法 FFT