14371: 【原4371】Fast Fourier Transform

题目

题目描述

author: sakiko 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4371

Description

给定一个$n$次多项式和一个$m$次多项式，请求出$F(x)$和$G(x)$的乘积。

Input Format

第一行两个整数分别表示$F(x)$和$G(x)$的次数。
第二行$n+1$个整数，从低到高表示$F(x)$的系数。
第三行$m+1$个整数，从低到高表示$G(x)$的系数。

Output Format

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

Sample Input 1

1 2
1 2
1 2 1

Sample Output 1

1 4 5 2

Sample Input 2

5 5
1 7 4 0 9 4
8 8 2 4 5 5

Sample Output 2

8 64 90 50 113 160 105 64 61 65 20

Data Range

对于$30\%$的数据，$n, m \le 3000$。
对于$100\%$的数据，$n, m \le 200000$,保证所有系数在0到9之间。

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！