代码

#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>

const int MAXN=270000;
const int DFT=1;
const int IDFT=-1;
const double PI=acos(-1);

struct Complex{
    double real;
    double imag;
    Complex(double r=0,double i=0){
        this->real=r;
        this->imag=i;
    }
};
Complex operator+(const Complex& a,const Complex& b){
    return Complex(a.real+b.real,a.imag+b.imag);
}
Complex operator-(const Complex& a,const Complex& b){
    return Complex(a.real-b.real,a.imag-b.imag);
}
Complex operator*(const Complex& a,const Complex& b){
    return Complex(a.real*b.real-a.imag*b.imag,a.real*b.imag+a.imag*b.real);
}

Complex a[MAXN],b[MAXN],c[MAXN];

int n;             //Length of a
int m;             //Length of b
int bln=1;         //Binary Length
int bct;           //Bit Count
int len;           //Length Sum
int rev[MAXN];     //Binary Reverse Sort

void Initialize();
void FFT(Complex*,int,int);

int main(){
    Initialize();
    FFT(a,bln,DFT);
    FFT(b,bln,DFT);
    for(int i=0;i<=bln;i++){
        c[i]=a[i]*b[i];
    }
    FFT(c,bln,IDFT);
    for(int i=0;i<=len;i++){
        printf("%d ",int(c[i].real/bln+0.5));
    }
    putchar('\n');
    return 0;
}

void FFT(Complex* a,int len,int opt){
    for(int i=0;i<len;i++)
        if(i<rev[i])
            std::swap(a[i],a[rev[i]]);
    for(int i=1;i<len;i<<=1){
        Complex wn=Complex(cos(PI/i),opt*sin(PI/i));
        int step=i<<1;
        for(int j=0;j<len;j+=step){
            Complex w=Complex(1,0);
            for(int k=0;k<i;k++,w=w*wn){
                Complex x=a[j+k];
                Complex y=w*a[j+k+i];
                a[j+k]=x+y;
                a[j+k+i]=x-y;
            }
        }
    }
}

void Initialize(){
    scanf("%d%d",&n,&m);
    len=n+m;
    while(bln<=len){
        bct++;
        bln<<=1;
    }
    for(int i=0;i<bln;i++){
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(bct-1));
    }
    for(int i=0;i<=n;i++){
        scanf("%lf",&a[i].real);
    }
    for(int i=0;i<=m;i++){
        scanf("%lf",&b[i].real);
    }
}

评测结果