当前位置: 代码迷 >> 综合 >> UOJ #34 多项式乘法
  详细解决方案

UOJ #34 多项式乘法

热度:3   发布时间:2024-01-19 02:05:48.0

这是一道模板题。

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

输入格式

第一行两个整数  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

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

FFT~

注意:

1.数组要开大,2*10^5+1会RE;

2.输出要四舍五入;

3.读入要写成%lf.


#include<cstdio>
#include<complex>
#include<cmath>
using namespace std;
#define E complex<double>
#define pi acos(-1)int n,m,l,r[300001];
E a[300001],b[300001];void fft(E *u,int v)
{for(int i=0;i<n;i++) if(i<r[i]) swap(u[i],u[r[i]]);for(int i=1;i<n;i<<=1){E wn(cos(pi/i),v*sin(pi/i));for(int j=0;j<n;j+=(i<<1)){E w(1,0);for(int k=0;k<i;k++,w*=wn){E x=u[j+k],y=u[i+j+k]*w;u[j+k]=x+y;u[i+j+k]=x-y;}}}if(v==-1) for(int i=0;i<n;i++) u[i]/=n;
}int main()
{scanf("%d%d",&n,&m);for(int i=0;i<=n;i++) scanf("%lf",&a[i]);for(int i=0;i<=m;i++) scanf("%lf",&b[i]);m+=n;for(n=1;n<=m;n<<=1) l++;for(int i=0;i<n;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));fft(a,1);fft(b,1);for(int i=0;i<n;i++) a[i]=a[i]*b[i];fft(a,-1);for(int i=0;i<=m;i++) printf("%d ",(int)(a[i].real()+0.5));return 0;
}


  相关解决方案