欢乐测速时间!

时间单位为跑一次次数为$2*10^5$的FFT所需时间。

以下时间都是大概的值,跑得时候可能出现玄学情况。

以及我的常数跟屎一样。。。各位dalao写的话可能会快不少。

  • 多项式乘法:6.3 (关于为啥不是3左右,因为我的乘法和FFT传进的多项式次数都是n,所以乘法需要扩2倍)
  • 多项式求逆:12
  • 多项式求ln:18.5
  • 多项式求exp:46.5 41(换了写法,具体看下面)

待测:

  • 多项式开根
  • 多项式取模
  • 其他多项式乱搞

有时间就测测吧。

更新:exp的写法改了,把每步乘法的范围缩小了一倍,快了一点。代码已经更新了。

测试用代码:

const LL P=998244353;
LL inv_v[MAXN],w_v[MAXN];

LL getPow(LL x,LL y){
    LL res=1;
    while(y){
        if(y&1) res=res*x%P;
        x=x*x%P;
        y>>=1;
    }
    return res;
}

void FFT(LL *a,int len,int flag){
    static int rev[MAXN];
    rev[0]=0;
    for(int i=1;i<len;i++)
        rev[i]=rev[i>>1]>>1|((i&1)?(len>>1):0);
    for(int i=0;i<len;i++)
        if(i<rev[i]) swap(a[i],a[rev[i]]);
    for(int l=2;l<=len;l<<=1){
        LL wn=w_v[l];
        int l2=l>>1;
        for(int i=0;i<len;i+=l){
            LL temp=1;
            for(int j=0;j<l2;j++){
                LL t1=a[i+j],t2=a[i+j+l2]*temp%P;
                a[i+j]=(t1+t2)%P;
                a[i+j+l2]=(t1-t2)%P;
                temp=temp*wn%P;
            }
        }
    }
    if(flag==-1){
        LL invn=getPow(len,P-2);
        for(int i=0;i<len;i++) a[i]=a[i]*invn%P;
        for(int i=1;i<len;i++)
            if(i<len-i) swap(a[i],a[len-i]);
    }
}

void mul(LL *a,LL *b,LL *c,int len){
    static LL t1[MAXN],t2[MAXN];
    for(int i=0;i<len;i++){
        t1[i]=a[i]; t2[i]=b[i];
        t1[i+len]=t2[i+len]=0;
    }
    FFT(t1,len<<1,1);
    FFT(t2,len<<1,1);
    for(int i=0;i<(len<<1);i++) t1[i]=t1[i]*t2[i]%P;
    FFT(t1,len<<1,-1);
    for(int i=0;i<(len<<1);i++) c[i]=t1[i];
}

void getInv(LL *a,LL *b,int len){
    if(len==1){
        b[0]=getPow(a[0],P-2);
        return;
    }
    getInv(a,b,len>>1);
    for(int i=(len>>1);i<len;i++) b[i]=0;
    static LL t1[MAXN],t2[MAXN];
    for(int i=0;i<len;i++){
        t1[i]=a[i]; t2[i]=b[i];
        t1[i+len]=t2[i+len]=0;
    }
    FFT(t1,len<<1,1); FFT(t2,len<<1,1);
    for(int i=0;i<(len<<1);i++)
        t1[i]=(2*t2[i]-t1[i]*t2[i]%P*t2[i])%P;
    FFT(t1,len<<1,-1);
    for(int i=0;i<len;i++) b[i]=t1[i];
}

void getln(LL *a,LL *b,int len){
    assert(a[0]==1);
    static LL t1[MAXN],t2[MAXN];
    for(int i=1;i<len;i++) t1[i-1]=a[i]*i%P;
    t1[len-1]=0;
    getInv(a,t2,len);
    mul(t1,t2,t1,len);
    for(int i=1;i<len;i++) b[i]=t1[i-1]*inv_v[i];
    b[0]=0;
}

void getExp(LL *a,LL *b,int len){
    if(len==1){
        assert(a[0]==0);
        b[0]=1;
        return;
    }
    static LL t1[MAXN],t2[MAXN],t3[MAXN],t4[MAXN];
    getExp(a,t1,len>>1);
    for(int i=0;i<(len>>1);i++) t4[i]=t1[i];
    getln(t1,t2,len);
    for(int i=0;i<(len>>1);i++)
        t3[i]=(t2[i+(len>>1)]-a[i+(len>>1)])%P;
    FFT(t1,len,1); FFT(t3,len,1);
    for(int i=0;i<len;i++) t3[i]=t1[i]*t3[i]%P;
    FFT(t3,len,-1);
    for(int i=0;i<(len>>1);i++){
        b[i]=t4[i];
        b[i+(len>>1)]=-t3[i];
    }
}

int n,sizew;

void init(){
    scanf("%d",&n);
    for(sizew=1;sizew<n;sizew<<=1);
    inv_v[1]=1;
    for(int i=2;i<=sizew*2;i++)
        inv_v[i]=-(P/i)*inv_v[P%i]%P;
    for(int l=1;l<MAXN;l<<=1)
        w_v[l]=getPow(3,(P-1)/l);
}

各位dalao发现我写得挫了或者有什么可以优化的地方,欢迎评论指出。