代码

#include <stdio.h>
#include <math.h>
#include <algorithm>
#define N 2100000
struct cp {
    double r,i;
    cp(double a=0,double b=0):r(a),i(b){}
};
inline cp operator+(cp a,cp b) {
    return (cp){a.r+b.r,a.i+b.i};
}
inline cp operator-(cp a,cp b) {
    return (cp){a.r-b.r,a.i-b.i};
}
inline cp operator*(cp a,cp b) {
    return (cp){a.r*b.r-a.i*b.i,a.r*b.i+b.r*a.i};
}
int L,rev[N];
void init(int n) {
    register int i,j;
    rev[0]=0;
    for(L=2;L<n;L<<=1);
    for(i=1;i<L;++i) {
    	rev[i]=rev[i>>1]>>1;
    	if(i&1) rev[i]|=L>>1;
	}
}
const double PI=acos(-1);
void FFT(cp *f,bool b) {
    register int i,j,k;
    register cp wn,w,t;
    for(i=0;i<L;++i) if(i<rev[i]) std::swap(f[i],f[rev[i]]);
    for(i=1;i<L;i<<=1) {
	    for(j=0;j<L;j+=i<<1) {
	    	wn=cp(cos(PI/i),sin(PI/i));
	    	if(b) wn.i=-wn.i;
	    	w=cp(1,0);
		    for(k=0;k<i;++k) {
			    t=w*f[j+k+i];
			    f[j+k+i]=f[j+k]-t;
			    f[j+k]=f[j+k]+t;
			    w=w*wn;
			}
		}
	}
	if(b) for(i=0;i<L;++i) f[i].r/=L;
}
int main() {
    static cp f[N],g[N];
    register int i,n,m,x;
    scanf("%d%d",&n,&m);
    for(i=0;i<=n;++i) {
	    scanf("%d",&x); f[i].r=x;
	}
    for(i=0;i<=m;++i) {
	    scanf("%d",&x); g[i].r=x;
	}
    init(n+m+1);
    FFT(f,0);
    FFT(g,0);
    for(i=0;i<L;++i) f[i]=f[i]*g[i];
    FFT(f,1);
    for(i=0;i<=n+m;++i) {
	    printf("%d ",(int)(f[i].r+.5));
	}
    return 0;
}

评测结果