「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;
}