fft模板题

fft模板题

题目描述

给定一个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)的系数。
样例数据

input

1 2
1 2
1 2 1

output

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

信息

难度
8
分类
(无)
标签
(无)
递交数
17
已通过
5
通过率
29%
上传者