代码

#include <bits/stdc++.h>
using namespace std;
typedef complex<double> complex_t;
const int MAXN = 2610000;

namespace FFT{
const double PI = acos(-1.0);
// op == 1 -> DFT, op == -1 -> IDFT
void fft(complex_t *P,int n,int op){
    static int r[MAXN];
    int len = 0;
    for(int i = 1;i<n;i<<=1) len++;
    for(int i = 0;i < n;i++)
        r[i] = (r[i>>1]>>1) | ((i&1) << (len-1)); 
    for(int i = 0;i < n;i++)
        if(i < r[i]) swap(P[i],P[r[i]]);
    for(int i = 1;i<n;i<<=1){
        complex_t x(cos(PI/i),op*sin(PI/i));
        for(int j = 0;j<n;j+=(i<<1)){
            complex_t y(1,0);
            for(int k = 0;k<i;k++,y*=x){
                complex_t p=P[j+k],q=y*P[i+j+k];
                P[j+k] = p+q,P[i+j+k]=p-q;
            }
        }
    }
}
}

int n,m;
complex_t a[MAXN],b[MAXN];

int main(){
    scanf("%d %d",&n,&m);
    int t;
    for(int i = 0;i<=n;i++){
        scanf("%d",&t);a[i] = t;
    }
    for(int i = 0;i<=m;i++){
        scanf("%d",&t);b[i] = t;
    }
    for(m+=n,n=1;n<=m;n<<=1);
    FFT::fft(a,n,1),FFT::fft(b,n,1);
    for(int i = 0;i<=n;i++)
        a[i] *= b[i]; 
    FFT::fft(a,n,-1);
    for(int i = 0;i<=m;i++)
        printf("%d ",int(a[i].real()/n + 0.5));
    return 0;
}

评测结果