「OI」快速数论变换 NTT

(未完待续)

$\texttt{NTT}$ 解决的是多项式乘法带模数的情况,可以说有些受模数的限制,数也比较大。但是速度快且不会有精度损失。

前置知识

未完待续。

生成子群

子群:群 $(S,\oplus),(S’,\oplus)$,满足 $S’\subset S$,则 $(S’,\oplus)$ 是 $$(S,\oplus)$ 的子群。

拉格朗日定理:$|S’|\mid|S|$ 证明需要用到陪集,得到陪集大小等于子群大小,每个陪集要么不相交要么相等,所有陪集的并是集合 $S$,那么显然成立。

生成子群:$a\in S$ 的生成子群 $\left<a\right>=\{a^{(k)},k\geq 1\}$,$a$ 是 $\left<a\right>$ 的生成元。

原根

快速数论变换 NTT

把 $\texttt{FFT}$ 中的 单位元 变换成 原根,就得到了 $\texttt{NTT}$。

简单代码实现

inline void NTT(reg ll a[],reg int f){
    for(reg int i=0;i<limit;++i)
        if(i<r[i])
            swap(a[i],a[r[i]]);
    for(reg int i=1;i<limit;i<<=1){
        reg ll w=pow(f==1?g:invg,(p-1)/(i<<1),p);
        for(reg int j=0;j<limit;j+=(i<<1)){
            reg ll e=1;
            for(reg int k=0;k<i;++k,e=(e*w)%p){
                reg ll x=a[j+k],y=e*a[j+k+i]%p;
                a[j+k]=(x+y)%p,a[j+k+i]=(x-y+p)%p;
            }
        }
    }
    return;
}