代码

#include<math.h>
#include<stdio.h>
const int MAXN=2400005 
const double tpi=acos(-1.0)
struct Complex
{
    double x;
    double y;
    Complex(double tX=0,double tY=0){x=tX,y=tY;}
}A[MAXN],B[MAXN];
int Rev[MAXN]={};
Complex operator + (Complex&a,Complex&b) {return Complex(a.x+b.x,a.y+b.y);}
Complex operator - (Complex&a,Complex&b) {return Complex(a.x-b.x,a.y-b.y);}
Complex operator * (Complex&a,Complex&b) {return Complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
int Limit=1,Siz=0;
void DFT(Complex*List,int Mode)
{
    for(int i=0;i<Limit;++i) if(i<Rev[i])
	{
		Complex t;
		t=List[Rev[i]];
		List[Rev[i]]=List[i];
		List[i]=t;
	}
    for(int Mid=1;Mid<Limit;Mid<<=1)
    {
        Complex Wn(cos(tpi/Mid),Mode*sin(tpi/Mid));
        for(int Len=Mid<<1,Pos=0;Pos<Limit;Pos+=Len)
        {
            Complex Base(1,0);
            for(int Sub=0;Sub<Mid;++Sub,Base=Base*Wn)
            {
                Complex X=List[Pos+Sub],Y=Base*List[Pos+Mid+Sub];
                List[Pos+Sub]=X+Y;
                List[Pos+Mid+Sub]=X-Y;
            }
        }
    }
}
void poly_multiply(unsigned *a, int N, unsigned *b, int M, unsigned *c)
{
    for(int i=0;i<=N;++i)A[i].x=a[i];
    for(int i=0;i<=M;++i)B[i].x=b[i];
    while(Limit<=N+M) Limit<<=1,++Siz;
    for(int i=0;i<Limit;++i) Rev[i]=(Rev[i>>1]>>1)|((i&1)<<(Siz-1));
    DFT(A,1);
    DFT(B,1);
    for(int i=0;i<=Limit;++i)A[i]=A[i]*B[i];
    DFT(A,-1);
    for(int i=0;i<=N+M;++i)c[i]=(int)(A[i].x/Limit+0.5);
}

评测结果