不想折磨自己了，以后都来这里贺。
卷积：
点击查看代码
poly NTT(poly a,int opt)
{
int len=a.size();
For(i,0,len-1){if(i<r[i])swap(a[i],a[r[i]]);}
for(int k=1;k<len;k<<=1)
{
ll wn=qpow(((opt==1)?g:inv_g),((mod-1)/(k<<1)));
for(int i=0;i<len;i+=(k<<1))
{
ll w=1;
for(int j=0;j<k;++j,(w*=wn)%=mod)
{
ll x=a[i+j],y=a[i+j+k];(y*=w)%=mod;
a[i+j]=x;Add(a[i+j],y);
a[i+j+k]=x;Sub(a[i+j+k],y);
}
}
}
if(opt==-1){For(i,0,len-1)(a[i]*=inv[len])%=mod;}
return a;
}
poly operator * (poly a,poly b)
{
int n=(a.size()-1),m=(b.size()-1);
int k=0;
while((1<<k)<=(n+m+1))++k;
For(i,1,((1<<k)-1))r[i]=((r[i>>1]>>1)|((i&1)<<(k-1)));
poly A,B;A.clear();B.clear();
A.resize(1<<k);B.resize(1<<k);
For(i,0,n)A[i]=a[i];For(i,0,m)B[i]=b[i];
A=NTT(A,1);B=NTT(B,1);
int len=A.size();For(i,0,len-1)(A[i]*=B[i])%=mod;
poly res=NTT(A,-1);
res.resize(n+m+1);return res;
}