NTT

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
/*
    注意：
    1. 用的时候c数组要开成2*(n1+n2)大小。
    2. g为P的原根。注意不能只根据g^fi(P)=1 (mod P)来判断g为原根，还要看是否有k<fi(P)，且使得g^k=1 (mod P)成立。如果存在k，则g不是原根。
*/

#define FOR(i,l,r) for(int i=(l);i<=(r);i++)
typedef long long LL;
const LL MOD=998244353;

const LL P=MOD,g=3;
void ntt(LL *a,size_t n,bool inv=false) {
    // inv为true时表示逆运算;
    LL w=1,d=pm(g,(P-1)/n,P),t;
    size_t i,j,c,s;
    if (inv){
        for (i=1,j=n-1;i<j;swap(a[i++],a[j--]));
        for (t=pm(n,P-2,P),i=0;i<n;++i) a[i]=a[i]*t%P;
    }
    for (s=n>>1;s;s>>=w=1,d=d*d%P)
    for (c=0;c<s;++c,w=w*d%P)
    for (i=c;i<n;i+=s<<1) {
        a[i|s]=(a[i]+P-(t=a[i|s]))*w%P;
        a[i]=(a[i]+t)%P;
    }
    for (i=1;i<n;++i) {
        for (j=0,s=i,c=n>>1;c;c>>=1,s>>=1) j=j<<1|s&1;
        if (i<j) swap(a[i],a[j]);
    }
}
void NTT(LL a[],int n1,LL b[],int n2,LL c[]) {  //求a[0,n1-1]和b[0,n2-1]的卷积c[0,n1+n2-1]
    int l;
    for (l=2;l<n1+n2-1;l<<=1);
    FOR (i,n1,l-1) a[i]=0;
    FOR (i,n2,l-1) b[i]=0;
    ntt(a,l); ntt(b,l);
    for (int i=0;i<l;++i) c[i]=a[i]*b[i]%MOD;
    ntt(c,l,1);
}
}}}

/*
    注意：
    1. 用的时候c数组要开成2*(n1+n2)大小。
    2. g为P的原根。注意不能只根据g^fi(P)=1 (mod P)来判断g为原根，还要看是否有k<fi(P)，且使得g^k=1 (mod P)成立。如果存在k，则g不是原根。
*/
#define FOR(i,l,r) for(int i=(l);i<=(r);i++)
typedef long long LL;
const LL MOD=998244353;
const LL P=MOD,g=3;
void ntt(LL *a,size_t n,bool inv=false) {
    // inv为true时表示逆运算;
    LL w=1,d=pm(g,(P-1)/n,P),t;
    size_t i,j,c,s;
    if (inv){
        for (i=1,j=n-1;i<j;swap(a[i++],a[j--]));
        for (t=pm(n,P-2,P),i=0;i<n;++i) a[i]=a[i]*t%P;
    }
    for (s=n>>1;s;s>>=w=1,d=d*d%P)
    for (c=0;c<s;++c,w=w*d%P)
    for (i=c;i<n;i+=s<<1) {
        a[i|s]=(a[i]+P-(t=a[i|s]))*w%P;
        a[i]=(a[i]+t)%P;
    }
    for (i=1;i<n;++i) {
        for (j=0,s=i,c=n>>1;c;c>>=1,s>>=1) j=j<<1|s&1;
        if (i<j) swap(a[i],a[j]);
    }
}
void NTT(LL a[],int n1,LL b[],int n2,LL c[]) {  //求a[0,n1-1]和b[0,n2-1]的卷积c[0,n1+n2-1]
    int l;
    for (l=2;l<n1+n2-1;l<<=1);
    FOR (i,n1,l-1) a[i]=0;
    FOR (i,n2,l-1) b[i]=0;
    ntt(a,l); ntt(b,l);
    for (int i=0;i<l;++i) c[i]=a[i]*b[i]%MOD;
    ntt(c,l,1);
}