社区讨论

关于FFT

ZZhuMingYang
学术版参与者 5已保存回复 7

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@loddfr3h
此快照首次捕获于
2023/10/31 04:47
2 年前
此快照最后确认于
2023/11/06 20:09
2 年前
查看原帖
如果FFT时最大次数超过了 会不会导致错误
例如下面代码（P4721分治FFT）
分治时将次数为0到(lmt-1)的c[]赋值为a[]
与tmp数组卷积
显然卷积最大次数超过了lmt
可AC 但我依稀记得次数超lmt会错。。
CPP
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);
}

回复

共 7 条回复，欢迎继续交流。

正在加载回复...