代码

#include <math.h>

    const double PI=3.141592653589793238462643383;
    const int N=2097160; // 2^21=2097152;
    
    int n,m,l;
    
    struct Complex {
        double r,i;

        Complex(double X=0.0,double Y=0.0): r(X), i(Y) { }
        friend Complex operator + (const Complex &a, const Complex &b) {
            return Complex(a.r+b.r, a.i+b.i);
        }
        friend Complex operator - (const Complex &a, const Complex &b) {
            return Complex(a.r-b.r, a.i-b.i); // 第一次写成a.i-b.r了。。。 
        }
        friend Complex operator * (const Complex &a, const Complex &b) {
            return Complex(a.r*b.r-a.i*b.i, a.r*b.i+a.i*b.r);
        }
        friend Complex operator ! (const Complex &a) {
            return Complex(a.r, -a.i);
        }
    }F[N],G[N];
    
    template <typename T>
    void myswap (T &a, T &b) {
        T Temp=a;
        a=b;
        b=Temp;
    }
    
    void DFT(Complex *a, int flag)
    {
        for(int i=0,j=0;i<l;++i) {
            if(i>j) myswap(a[i],a[j]);
            for(int k=l>>1;(j^=k)<k;k>>=1);
        }
        register Complex x,y; // 不知道能不能加register。 
        for(int i=1;i<l;i<<=1) {
        	Complex w(cos(PI/i),flag*sin(PI/i));
        	for(int j=0;j<l;j+=i<<1) {
        		Complex e(1,0);
        		for(int k=0;k<i;++k,e=e*w) {
        			x=a[j+k]; y=a[j+k+i]*e;
        			a[j+k]=x+y; a[j+k+i]=x-y;
        		}
        	}
        }
        if(flag==-1) 
        	for(int i=0;i<l;++i) 
        		a[i].r=(int)(a[i].r/l+0.5);
    }


void poly_multiply(Complex *a, int n, Complex *b, int m, Complex *c)
{
    int l; while(l<=(n+m)) l<<=1;
    DFT(a,1); DFT(b,1); for(register int i=0;i<l;++i) a[i]=a[i]*b[i]; DFT(a,-1); for(int i=0;i<=n+m;++i) c[i]=a[i].r;
}

评测结果