...

我只能说大概懂，但是现在用不到，没细学

代码就是写个模版，到博客里吃灰吧（bushi

 

#include<bits/stdc++.h>

using namespace std;
const int N=6e6+7;
const double pi=acos(-1);

int n,m;
struct node
{
    double x,y;
    node operator + (const node&t) const 
    {
        return {x+t.x ,y+t.y};
    }
    node operator - (const node&t) const
    {
        return {x-t.x ,y-t.y};
    }
    node operator * (const node&t) const
    {
        return {x*t.x -y*t.y ,x*t.y+y*t.x};
    }
}a[N],b[N];

int rev[N],bit,cnt;

void fft(node a[],int inv)
{
    for(int i=0;i<cnt;i++)
        if(i<rev[i])
            swap(a[i],a[rev[i]]);
    
    for(int mid=1;mid<cnt;mid<<=1)
    {
        node wl=node({cos(pi/mid),inv*sin(pi/mid)});
        
        for(int i=0;i<cnt;i+=(mid<<1))
        {
            node wr=node({1,0});
            
            for(int j=0;j<mid;j++,wr=wr*wl)
            {
                node x=a[i+j],y=wr*a[i+j+mid];
                a[i+j]=x+y;
                a[i+j+mid]=x-y;
            }
            
        }
        
    }
            
    return ;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    
    for(int i=0;i<=n;i++)
    cin>>a[i].x;
    for(int i=0;i<=m;i++)
    cin>>b[i].x;
    
    while((1<<bit)<n+m+1)
    bit++;
    cnt=1<<bit;
    
    for(int i=0;i<cnt;i++)
    {
        rev[i]=( (rev[i>>1]>>1)|((i&1)<<(bit-1)) );
    }
    
    fft(a,1);
    fft(b,1);
    
    for(int i=0;i<cnt;i++)
    a[i]=a[i]*b[i];
    fft(a,-1);
    
    for(int i=0;i<=n+m;i++)
    cout<<(int)(a[i].x/cnt+0.5)<<' ';

    return 0;
}