4164: 【模板】多项式乘法(FFT&NTT)

时间限制:5000 ms 内存限制:256 MB
上传者:
提交:6 通过:3

题目描述

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

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





数据很弱,希望各位用FFT或者NTT解决,而不是暴力

输入格式

第一行两个整数 n,m

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

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

输出格式

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

输入样例 复制

1 2
1 2
1 2 1

输出样例 复制

1 4 5 2

数据范围与提示

分类标签