关于FFT
  • 板块学术版
  • 楼主ZhuMingYang
  • 当前回复7
  • 已保存回复7
  • 发布时间2020/8/16 09:48
  • 上次更新2023/11/6 20:09:16
查看原帖
关于FFT
128523
ZhuMingYang楼主2020/8/16 09:48

如果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);
}
2020/8/16 09:48
加载中...