这篇咕了很久... 现在填上吧 (草率).

作用和 FFT 是类似的, 只是要取模而已.

前置知识

FFT, 原根 .

例题

和 FFT 的是一样的

• 洛谷 P3803 [模板]多项式乘法 (FFT)
• 洛谷 P1919 [模板]A*B Problem 升级版 (FFT 快速傅里叶)

整体思路

因为原根有和单位根类似的性质, 都可以唯一地表示一个数 (但是原根要在模意义下).

暴力地去求多项式卷积的复杂度显然是 $\Theta(n^2)$ 的.

引自 算法导论

好的显然和 FFT 是一样的, 只是把里面的 $\omega$ 换成了 $g$ 而已.

Code

/*jly是模数(%%%jly),grt是对应原根*/
int qow[400005],inv[400005];

inline void init() {
    int iv=ksm(grt,jly-2);
    for (int i=1;i<262145;i<<=1) {
        qow[i]=ksm(grt,(jly-1)/i);
        inv[i]=ksm(iv,(jly-1)/i);
    }
}

inline void NTT(int *a,int n,bool f,bool u=false) {
    static int k,r[400005];
    int g0,gx,b,c;
    if (u) {
        k=0;
        for (int i=2;i<n;i<<=1) ++k;
        for (int i=0;i<n;++i)
            r[i]=(r[i>>1]>>1)|((i&1)<<k);
    }
    for (int i=0;i<n;++i) if (i<r[i])
        swap(a[i],a[r[i]]);
    for (int i=1;i<n;i<<=1) {
        g0=f?inv[i<<1]:qow[i<<1]; /*这里要预处理出原根的幂和逆元*/
        for (int j=0;j<n;j+=(i<<1)) {
            gx=1;
            for (int k=0;k<i;++k) {
                b=a[j+k]; c=(long long)gx*a[i+j+k]%jly;
                a[j+k]=mjly(b+c); a[i+j+k]=mjly(b-c+jly);
                gx=(long long)g0*gx%jly;
            }
        }
    }
    if (f) {
        int iv=ksm(n,jly-2);
        for (int i=0;i<n;++i)
            a[i]=(long long)a[i]*iv%jly;
    }
}