#34. 多项式乘法

 统计  描述 提交 自定义测试

这是一道模板题。

给你两个多项式，请输出乘起来后的多项式。

输入格式

第一行两个整数  n n 和  m m，分别表示两个多项式的次数。

第二行  n+1 n+1 个整数，分别表示第一个多项式的  0 0 到  n n 次项前的系数。

第三行  m+1 m+1 个整数，分别表示第一个多项式的  0 0 到  m m 次项前的系数。

输出格式

一行  n+m+1 n+m+1 个整数，分别表示乘起来后的多项式的  0 0 到  n+m n+m 次项前的系数。

样例一

input

1 2 1 2 1 2 1

output

1 4 5 2

explanation

(1+2x)⋅(1+2x+x2)=1+4x+5x2+2x3 (1+2x)⋅(1+2x+x2)=1+4x+5x2+2x3。

限制与约定

0≤n,m≤105 0≤n,m≤105，保证输入中的系数大于等于  0 0 且小于等于  9 9。

时间限制： 1s 1s

空间限制： 256MB

由于博主是个智障，数学没学好， 复数都不会，所以此题仅仅是挖坑，抄了下模板

等到noip，我一定会更新（AFO）的

#include<bits/stdc++.h> #define pi acos(-1) using namespace std; typedef complex<double> E; int n,m; E a[262145],b[262145]; void fft( E *x, int n, int type ){ if( n == 1 ) return ; E l[n>>1], r[n>>1]; for( int i = 0; i < n; i += 2 ) l[i>>1] = x[i], r[i>>1] = x[i+1]; fft( l, n>>1, type ); fft( r, n>>1, type ); E wn(cos(2*pi/n),sin(type*2*pi/n)),w(1,0),t; for( int i = 0; i < n>>1; i++, w *= wn ) t = w*r[i], x[i] = l[i]+t, x[i+(n>>1)] = l[i]-t; } int main(){ scanf("%d%d", &n, &m); for( int i = 0,x; i <= n; i++ ) scanf("%d", &x), a[i] = x; for( int i = 0,x; i <= m; i++ ) scanf("%d", &x), b[i] = x; m = n+m; for( n = 1; n <= m; n <<= 1 ); fft( a, n, 1 ); fft( b, n, 1 ); for( int i = 0; i <= n; i++ ) a[i] *= b[i]; fft( a, n, -1 ); for( int i = 0; i <= m; i++ ) printf("%d ", (int)(a[i].real()/n+0.5)); return 0; }