代码

#include<iostream>
#include<cstdio>
#include<cmath>

const double pi=acos(-1);

struct complex{
    double a,b;
    complex operator = (const complex y){return (complex){a=y.a,b=y.b};}
};
complex operator + (const complex x,const complex y){return (complex){x.a+y.a,x.b+y.b};}
complex operator - (const complex x,const complex y){return (complex){x.a-y.a,x.b-y.b};}
complex operator * (const complex x,const complex y){return (complex){x.a*y.a-x.b*y.b,x.a*y.b+x.b*y.a};}
complex operator *= (complex &x,const complex y){return x=x*y;}

int N=1,r,n,m;
complex A[5000000],B[5000000],C[10000000];

void FFT(complex *V,int N,int l,int f){
    int rev[N+5];rev[0]=0;
    for (int i=1;i<=N;i++){
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
        if (i<rev[i]) std::swap(V[i],V[rev[i]]);
    }
    for (int i=1;i<N;i<<=1){
        complex w0={cos(pi/i),f*sin(pi/i)};
        for (int S=i<<1,j=0;j<N;j+=S){

            complex w={1,0};
            for (int k=0;k<i;k++,w*=w0){
                complex x=V[k+j],y=w*V[k+i+j];
                V[k+j]=x+y;
                V[k+i+j]=x-y;
            }
        }
    }
    if (f==-1) for (int i=0;i<N;i++) V[i].a/=N;
}
void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c)
{
    while (N<=n+m){N<<=1;r++;}
    FFT(a,N,r,1);
    FFT(b,N,r,1);
    for (int i=0;i<=N;i++) c[i]=a[i]*b[i];
    FFT(c,N,r,-1);
}

评测结果