NTT学习笔记

## NTT学习笔记 嗯，之前已经学习过了[FFT](https://www.luogu.com.cn/blog/c2522943959/fft-xue-xi-bi-ji)，现在学习一下它的改进版NTT（即数论快速变换） FFT需要用到复数，常数大，容易掉精度，而且无法取模。 先来定义**原根**对于质数$p$，若存在一个$g\in[2,p-1]$满足对任意$i\in[1,p-1]$有$g^i\ mod\ p$互不相同，则称$g$是$p$的**原根** 值得一提的是，998244353的原根是3 FFT中，单位根作为带入的点值。类似的，原根也可以作为点值带入，它有与单位根相似的性质。 在NTT中，“单位根”取$g^{p-1}/{2len}$。通常取$p=998244353,g=3$ 时间复杂度同样是$\Theta(nlogn)$，但常数更小 NTT模板： ```cpp ll a[MAXN],b[MAXN],status[MAXN]; void NTT(ll* a,ll len,ll type) { for(ll i=0;i<len;++i) if(status[i]>i)std::swap(a[i],a[status[i]]); for(ll cur=1;cur<len;cur<<=1) { ll root=Qpow(3,(mod-1)/(cur<<1));//单位根 if(type==-1)root=Qpow(root,mod-2);//IDFT时要取逆元 for(ll j=0;j<len;j+=(cur<<1)) { ll w=1; for(ll k=0;k<cur;++k,w=(w*root)%mod)//合并 { ll x=a[j+k],y=w*a[j+cur+k]; a[j+k]=(x+y)%mod; a[j+cur+k]=((x-y)%mod+mod)%mod; } } } } ```