代码

using namespace std;

const int MAXN=1e7+10;

const double pi=acos(-1.0);

struct Complex
{
    double x,y;
    Complex (double xx=0,double yy=0){x=xx,y=yy;}

    Complex operator + (const Complex &b)
    {
        return Complex(this->x+b.x,this->y+b.y);
    }
    Complex operator - (const Complex &b)
    {
        return Complex(this->x-b.x,this->y-b.y);
    }
    Complex operator * (const Complex &b)
    {
        return Complex(this->x*b.x-this->y*b.y,this->x*b.y+this->y*b.x);
    }
}a[MAXN],b[MAXN];

int n,m;
int l,r[MAXN];
int limit=1;

void FFT(Complex *A,int opt)
{
    for(int i=0;i<limit;i++)
    {
        if(i<r[i])
        {
            swap(A[i],A[r[i]]);
        }
    }
    for(int mid=1;mid<limit;mid<<=1)
    {
        Complex Wn(cos(pi/mid),opt*sin(pi/mid));
        for(int R=mid<<1,j=0;j<limit;j+=R)
        {
            Complex w(1,0);
            for(int k=0;k<mid;k++,w=w*Wn)
            {
                Complex x=A[j+k],y=w*A[j+mid+k];
                A[j+k]=x+y;
                A[j+mid+k]=x-y;
            }
        }
    }
}

void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c)
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<=n;i++)
    {
        cin>>a[i].x;
    }
    for(int j=0;j<=m;j++)
    {
        cin>>b[j].x;
    }
    while(limit<=n+m)
    {
        limit<<=1;
        ++l;
    }
    for(int i=0;i<limit;i++)
    {
        r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    }
    FFT(a,1);
    FFT(b,1);
    for(int i=0;i<=limit;i++)
    {
        a[i]=a[i]*b[i];
    }
    FFT(a,-1);
    for(int i=0;i<=n+m;i++)
    {
        c[i]=(int)(a[i].x/limit+0.5);
    }
}

评测结果