如果FFT时最大次数超过了 会不会导致错误
例如下面代码(P4721分治FFT)
分治时将次数为0到(lmt-1)的c[]赋值为a[]
与tmp数组卷积
显然卷积最大次数超过了lmt
可AC 但我依稀记得次数超lmt会错。。
inline void getrev(int n)
{
lmt=1;
while(lmt<n) lmt<<=1;
for(int i=1;i<lmt;++i)
r[i]=(r[i>>1]>>1)|((i&1)?lmt>>1:0);
}
void cdq(int l,int r)
{
if(l==r){
if(l==0) b[l]=1;
return;
};
int mid=(l+r)>>1;
cdq(l,mid);
getrev(r-l+1);
for(int i=l;i<=mid;++i) tmp[i-l]=b[i];
for(int i=mid-l+1;i<lmt;++i) tmp[i]=0;
for(int i=0;i<lmt;++i) c[i]=a[i];
NTT(tmp,1),NTT(c,1);
for(int i=0;i<lmt;++i) tmp[i]=(ll)tmp[i]*c[i]%mod;
NTT(tmp,-1);
for(int i=mid+1;i<=r;++i) b[i]=(b[i]+tmp[i-l])%mod;
cdq(mid+1,r);
}