代码

#include<cstdio>
#include<cmath>
#include<complex>
#define N 400005 
using namespace std;
typedef complex<double>comp;
const double pi=acos(-1);
int n,m,a[N],b[N],L,r[N];
comp w1[N],w2[N];
void FFT(comp *A,int o)
{
    for(int i=0;i<n;++i)if(i<r[i])swap(A[i],A[r[i]]);
    for(int i=1;i<n;i<<=1)
    {
        comp wn(cos(pi/i),sin(o*pi/i)),a,b;
        for(int j=0;j<n;j+=(i<<1))
        {
            comp w(1,0);
            for(int k=0;k<i;++k,w*=wn)
            {
                a=A[j+k];b=A[i+j+k]*w;
                A[j+k]=a+b;A[i+j+k]=a-b;
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;++i)scanf("%d",&a[i]);
    for(int i=0;i<=m;++i)scanf("%d",&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)));
        w1[i]=a[i];w2[i]=b[i];
    }
    FFT(w1,1);FFT(w2,1);
    for(int i=0;i<n;++i)w1[i]*=w2[i];
    FFT(w1,-1);
    for(int i=0;i<=m;++i)printf("%d ",(int)(w1[i].real()/n+0.5));
    return 0;
}

评测结果