代码

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 2e6 + 100;
const double pi = acos(-1);
struct complex{
    double x,y;
    complex operator + (const complex &rhs)const{return complex{x + rhs.x,y + rhs.y};}
    complex operator - (const complex &rhs)const{return complex{x - rhs.x,y - rhs.y};}
    complex operator * (const complex &rhs)const{return complex{x * rhs.x - y * rhs.y,x * rhs.y + y * rhs.x};}
}F[maxn << 1],G[maxn << 1];
int tr[maxn << 1],n,m;
inline void fft(complex *f,int flag){
    for(int i = 0;i < n;i++)
        if(i < tr[i])swap(f[i],f[tr[i]]);
    for(int p = 2;p <= n;p <<= 1){
        int len = p >> 1;
        complex unit{cos(2 * pi / p),sin(2 * pi / p) * flag};
        for(int k = 0;k < n;k += p){
            complex g{1,0};
            for(int l = k;l < k + len;l++){
                complex t = f[l + len] * g;
                f[l + len] = f[l] - t;
                f[l] = f[l] + t;
                g = g * unit;
            }
        }
    }
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i = 0;i <= n;i++)scanf("%lf",&F[i].x);
    for(int i = 0;i <= m;i++)scanf("%lf",&G[i].x);
    for(m += n,n = 1;n <= m;n <<= 1);
    for(int i = 0;i < n;i++)
        tr[i] = (tr[i >> 1] >> 1) | ((i & 1) ? (n >> 1) : 0);
    fft(F,1),fft(G,1);
    for(int i = 0;i < n;i++)F[i] = F[i] * G[i];
    fft(F,-1);
    for(int i = 0;i <= m;i++)printf("%d ",(int)(F[i].x / n + 0.49));
    return 0;
}

评测结果