代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
const double pi=acos(-1);
using namespace std;
class complex
{
    public:
        double real,imag;
        complex(double x=0.0,double y=0.0)
        {
            real=x,imag=y;
        }
        complex operator +(const complex &x)
        {
            return complex(real+x.real,imag+x.imag);
        }
        complex operator -(const complex &x)
        {
            return complex(real-x.real,imag-x.imag);
        }
        complex operator *(const complex &x)
        {
            return complex(real*x.real-imag*x.imag,real*x.imag+imag*x.real);
        }
}A[1000010],B[1000010],C[1000010];
int R[1000010];
void fft(complex *A,int lim,int flag)
{
    for(int i=0;i<lim;i++)
    {
        if(i<R[i])swap(A[i],A[R[i]]);
    }
    for(int j=1;j<lim;j<<=1)
    {
        complex bas(cos(pi/j),flag*sin(pi/j));
        for(int i=0;i<lim;i+=(j<<1))
        {
            complex t(1,0);
            for(int l=0;l<j;l++,t=t*bas)
            {
                complex nx=A[i+l],ny=t*A[i+j+l];
                A[i+l]=nx+ny;
                A[i+j+l]=nx-ny;
            }
        }
    }
}
int n,m;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;i++)scanf("%lf",&A[i].real);
    for(int i=0;i<=m;i++)scanf("%lf",&B[i].real);
    int lognum=0,tmp=1;
    while(tmp<=n+m)tmp<<=1,lognum++;
    for(int i=0;i<tmp;i++)R[i]=(R[i>>1]>>1)|((i&1)<<(lognum-1));
    fft(A,tmp,1);
    fft(B,tmp,1);
    for(int i=0;i<=tmp;i++)C[i]=A[i]*B[i];
    fft(C,tmp,-1);
    for(int i=0;i<=n+m;i++)printf("%d ",(int)(C[i].real/tmp+0.5));
    return 0;
}

评测结果