代码

#include<bits/stdc++.h>
#define cir(i,a,b) for(int i=a;i<b;++i)
using namespace std;
using complf=complex<double>;
namespace poly{
    static constexpr auto pi=acos(-1);
    auto change(vector<complf>&a,const int n){
        vector<int> rev(n);
        cir(i,0,n){
            rev[i]=(rev[i>>1]>>1)|((n>>1)*(i&1));
        }
        cir(i,0,n) if(i<rev[i]) swap(a[i],a[rev[i]]);
    }
    template<const int type>
    auto fft(vector<complf>&a,const int n){
        change(a,n);
        for(auto h=2;h<n+1;h<<=1){
            const auto wx=complf(cos(pi*2/h),sin(pi*2*type/h));
            const auto midh=h/2;
            for(auto i=0;i<n;i+=h){
                auto u=complf(1,0);
                cir(k,i,i+midh){
                    const auto wy=u*a[k+midh];
                    a[k+midh]=a[k]-wy;a[k]+=wy;
                    u*=wx;
                }
            }
        }
        if(type==-1) for(auto&i:a) i/=n;
    }
    auto mul(vector<int> a,vector<int> b){
        const auto n=1<<((int)(log2(a.size()+b.size()))+1);
        vector<complf> fx(n);
        cir(i,0,(int)(a.size())) fx[i]+=complf(a[i],0);
        cir(i,0,(int)(b.size())) fx[i]+=complf(0,b[i]);
        fft<1>(fx,n);
        for(auto&i:fx) i*=i;
        fft<-1>(fx,n);
        vector<int> ans(n);
        cir(i,0,n) ans[i]=round(fx[i].imag()/2);
        return ans;
    }
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n,m;cin>>n>>m;++n;++m;
    vector<int> a(n),b(m);
    for(auto&i:a) cin>>i;
    for(auto&i:b) cin>>i;
    const auto ans=poly::mul(a,b);
    cir(i,0,n+m-1) cout<<ans[i]<<' ';
    cout<<'\n';
    return 0;
}

评测结果