代码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=1100000;
const double pi=acos(-1);
const double pi2=pi*2;
int n,x,lena,lenb,res[MAXN];
char sa[MAXN],sb[MAXN];
struct cp{
	double rez,imz;
	cp (double x=0,double y=0){
        rez=x;
        imz=y;
    }
    cp operator+(const cp &a) const{
        return cp(rez+a.rez,imz+a.imz);
    } 
    cp operator-(const cp &a) const{
        return cp(rez-a.rez,imz-a.imz);
    }
    cp operator*(const cp &a) const{
        return cp(rez*a.rez-imz*a.imz,rez*a.imz+imz*a.rez);
    }  
    cp conjugate(){
        return cp(rez,-imz);
    }
} a[MAXN],b[MAXN],omg[MAXN],inv[MAXN];
void FFT(cp *a,cp *omg){
    int lim=0;
    while ((1<<lim)<n) lim++;
    for (int i=0;i<n;i++){
        int t=0;
        for (int j=0;j<lim;j++)
            if (i&1<<j) t|=(1<<(lim-j-1));
        if (i<t) swap(a[i],a[t]);
    }
    for (int l=2;l<=n;l<<=1){
        int m=l>>1;
        for (cp *p=a;p!=a+n;p+=l)
            for (int i=0;i<m;i++){
                cp t=omg[n/l*i]*p[i+m];
                p[i+m]=p[i]-t;
                p[i]=p[i]+t;
            }
    }
}
int main(){
    scanf("%d%d",&lena,&lenb);
    lena++; lenb++;
    n=1;
    while (n<lena+lenb) n<<=1;
    for (int i=0;i<lena;i++){
        scanf("%d",&x);
        a[lena-i-1].rez=x;
    }
    for (int i=0;i<lenb;i++){
        scanf("%d",&x);
        b[lenb-i-1].rez=x;
    }
    for (int i=0;i<n;i++){
        omg[i]=cp(cos(pi2*i/n),sin(pi2*i/n));
        inv[i]=omg[i].conjugate();
    }
    FFT(a,omg); FFT(b,omg);
    for (int i=0;i<n;i++) a[i]=a[i]*b[i];
    FFT(a,inv);
    for (int i=0;i<n;i++) res[i]=floor(a[i].rez/n+0.5);
    for (int i=lena+lenb-2;i>0;i--) printf("%d ",res[i]);
    printf("%d\n",res[0]);
    return 0;
}

评测结果