#34. 多项式乘法

统计

这是一道模板题。

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

输入格式

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

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

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

输出格式

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

样例一

input

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≤1050≤n,m≤105，保证输入中的系数大于等于 00 且小于等于 99。

时间限制：1s1s

空间限制：256MB256MB

下载

样例数据下载

#include<cmath>

#include<cstdio>

#include<complex>

using namespace std;

typedef complex<double> E;

const double Pi=acos(-);

const int N=3e5+;

int n,m,L,R[N];

E a[N],b[N];

void FFT(E *a,int f){

    for(int i=;i<n;i++) if(i<R[i]) swap(a[i],a[R[i]]);

    for(int i=;i<n;i<<=){

        E wn(cos(Pi/i),f*sin(Pi/i));

        for(int p=i<<,j=;j<n;j+=p){

            E w(,);

            for(int k=;k<i;k++,w*=wn){

                E x=a[j+k],y=w*a[j+k+i];

                a[j+k]=x+y;a[j+k+i]=x-y;

            }

        }

    }

}

int main(){

    scanf("%d%d",&n,&m);

    for(int i=,x;i<=n;i++) scanf("%d",&x),a[i]=x;

    for(int i=,x;i<=m;i++) scanf("%d",&x),b[i]=x;

    for(m+=n,n=;n<=m;n<<=) L++;

    for(int i=;i<n;i++) R[i]=(R[i>>]>>)|((i&)<<(L-));

    FFT(a,);FFT(b,);

    for(int i=;i<=n;i++) a[i]*=b[i];

    FFT(a,-);

    for(int i=;i<=m;i++) printf("%d ",(int)(a[i].real()/n+0.5));

    return ;

}

/*

比着敲完就算了，FFT理解，来日方长。

zky神犇写的非常详细

http://blog.csdn.net/iamzky/article/details/22712347

*/

巴特西

UR#34. 多项式乘法