猫史档案馆

内容同时发布于我的博客（洛谷uid：246979）。

非常感谢慕斯的帮助。

//重载运算符扩域至复数 
struct Complex
{
    Complex (double xx=0,double yy=0){x=xx,y=yy;}double x,y;
    Complex operator + (Complex const &B) const {return Complex(x+B.x,y+B.y);}
    Complex operator - (Complex const &B) const {return Complex(x-B.x,y-B.y);}
    Complex operator * (Complex const &B) const {return Complex(x*B.x-y*B.y,x*B.y+y*B.x);}
}f[2700000],g[2700000];

//FFT,flag控制求值或插值(正/逆)
void fft(Complex *f,int len,bool flag)
{
    if(len==1)return;
    Complex *fl=f,*fr=f+len/2;
    for(int k=0;k<len;k++)tmp[k]=f[k];
    for(int k=0;k<len/2;k++)
        fl[k]=tmp[k<<1],fr[k]=tmp[k<<1|1];
    //递归分治求解 
    fft(fl,len/2,flag),fft(fr,len/2,flag);
    //buf为k单位根,tG为起始1次单位根 
    Complex tG(cos(2*Pi/len),sin(2*Pi/len)),buf(1,0);
    if(flag)tG.y*=-1;//DFT为负,ISFT为正
    //求出而序列的点值 
    for(int k=0;k<len/2;k++)
        tmp[k]=fl[k]+buf*fr[k], 
        tmp[k+len/2]=fl[k]-buf*fr[k],
        buf=buf*tG;
    for(int k=0;k<len;k++)f[k]=tmp[k];
}

//重载运算符,复数 
struct Complex
{
    Complex (double xx=0,double yy=0){x=xx,y=yy;}double x,y;
    Complex operator + (Complex const &B) const {return Complex(x+B.x,y+B.y);}
    Complex operator - (Complex const &B) const {return Complex(x-B.x,y-B.y);}
    Complex operator * (Complex const &B) const {return Complex(x*B.x-y*B.y,x*B.y+y*B.x);}
}f[2700000],g[2700000];
//FFT,flag控制求值或插值(正/逆)
void fft(Complex *f,bool 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 tG(cos(2*Pi/p),sin(2*Pi/p));
        if(flag)tG.y*=-1;
        //处理以p为段长的每一段 
        for(int k=0;k<n;k+=p)
        {
            Complex buf(1,0);
            //代入单位根逐次数求解
            for(int l=k;l<k+len;l++)
            {
                Complex tt=buf*f[len+l];
                f[len+l]=f[l]-tt,f[l]=f[l]+tt,buf=buf*tG;
            }
        }
    }
}

void mul(){
    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,0);
    for(int i=0;i<=m;i++)
        ans[i]=(int)(f[i].x/n+0.5);
}

 

祝大家学习愉快（

可以在评论区回复。