代码

#include<bits/stdc++.h>
#define pi acos(-1)
using namespace std;
complex<double> a[2621450],b[2621450];
int n,m,l,r[2621450];
void FFT(complex<double> *a,int f){
    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){
        complex<double> wn(cos(pi/i),f*sin(pi/i));
        int p=i<<1;
        for(int j=0;j<n;j+=p){
            complex<double> w(1,0);
            for(int k=0;k<i;k++,w*=wn){
                complex<double> 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=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));
    FFT(a,1);
    FFT(b,1);
    for(int i=0;i<=n;i++)
        a[i]*=b[i];
    FFT(a,-1);
    for(int i=0;i<=m;i++)
        printf("%d ",int(a[i].real()/n+0.5));
}

评测结果