代码

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int N=5e6+5;

//¸´ÊýÀàÐÍ 
const double Pi=acos(-1.0);    //¦ÐµÄÖµ
struct complex {  //¸´ÊýÀàÐÍ 
	double x,y;   //xΪ³£Êý£¬yΪsqrt(-1)µÄϵÊý 
	complex (double xx=0,double yy=0) { x=xx,y=yy; }
} A[N],B[N],Omega[N];
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 len,n,m,r[N],l; 
inline complex Conj(complex z) { return complex(z.x,-z.y); }

//FFT µãÖµ±íʾ·¨ÓëϵÊý±íʾ·¨µÄ»¥»» 
void FFT(complex *A,bool P) {  //AΪϵÊý£¬PµÄ½âÊͼûÏÂÃæ
	for (int i=0; i<len; i++)
		if (i<r[i]) swap(A[i],A[r[i]]);  //Çó³öµü´úµÄÐòÁÐ
	for (int mid=1; mid<len; mid<<=1) {  //Õâ´ÎÒªºÏ²¢µÄÇø¼äµÄ³¤¶ÈµÄÒ»°ë
		complex Wn=P?Conj(Omega[len/mid>>1]):Omega[len/mid>>1];  //ÓÃÅ·À­¶¨ÀíÇóµ¥Î»¸ù		 
		for (int j=0; j<len; j+=(mid<<1)) { //(mid<<1)ΪÇø¼ä³¤¶È£¬jΪµ±Ç°Î»ÖÃ
			complex w=complex(1,0);  //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;     //×ó±ßµÄ´ð°¸ÓëÓұߵĴð°¸Ö»ÓÐϵÊý²»Í¬
			}
		}
	}
}		 

int main() {
	scanf("%d%d",&n,&m);
	for (int i=0; i<=n; i++) scanf("%lf",&A[i].x); //´ú±íAÖÐx^0,x^1,x^2¡­¡­µÄϵÊý 
	for (int i=0; i<=m; i++) scanf("%lf",&B[i].x); //ºÍAÒâÒåÏàËÆ
	len=1; while (len<=n+m) len<<=1,l++;          //lenΪµ¥Î»wµÄ×î´óÃݴη½
	for (int i=0; i<len; i++)
		r[i]=(r[i>>1]>>1)|((i&1)<<(l-1)); 
	Omega[0]=complex(1,0), 
	Omega[1]=complex(cos(2*Pi/len),sin(2*Pi/len));
	for (int i=2; i<len; i++)
		Omega[i]=Omega[i-1]*Omega[1]; //printf("%.2lf %.2lf\n",Omega[2].x,Omega[2].y);
	//ºûµû¶¨Àí
	// ÔÚÔ­ÐòÁÐÖÐ i Óë i/2 µÄ¹ØϵÊÇ £º i¿ÉÒÔ¿´×öÊÇi/2µÄ¶þ½øÖÆÉϵÄÿһλ×óÒÆһλµÃÀ´
    // ÄÇôÔÚ·´×ªºóµÄÊý×éÖоÍÐèÒªÓÒÒÆһλ£¬Í¬Ê±ÌØÊâ´¦ÀíÒ»ÏÂÆæÊý  
    
	FFT(A,0); FFT(B,0);     //1±íʾ´ÓϵÊý->µãÖµ,-1±íʾ´ÓµãÖµ->ϵÊý   
	for (int i=0; i<=len; i++) A[i]=A[i]*B[i]; //ÏòÁ¿³Ë·¨
	FFT(A,1);    
	for (int i=0; i<=n+m; i++)   
		printf("%d ",(int)(A[i].x/len+0.5));   //ËÄÉáÎåÈ룬ÕâÀï³ýÒÔlenÊÇÒòΪ¹«Ê½£¨¼û¸½±¾£©
	return 0;
}

评测结果