NTT

先学习FFT

由于FFT是使用复数运算，精度并不好，而且也无法取模，所以有了NTT（快速数论变换）。

建议先完全理解FFT后再学习NTT。

NTT使用与单位根性质相似的原根来代替单位根。

定义：设\(m\)是正整数，\(a\)是整数，若\(a\)模\(m\)的阶等于\(φ(m)\)，则称\(a\)为模\(m\)的一个原根。

如果你不知道阶

定义：对于\(an≡1(modp)an≡1(modp)\)最小的\(n\)，我们称之为\(a\)模\(p\)的阶,记做\(δp(a)\)

如果你懒得看麻烦的定义，可以直接从这里开始看。

\(g\)表示质数\(p\)的原根

998244353 的原根是3，3在模998244353的逆元是332748118。

最最重要的性质我不会证但我会背：

\[\omega_n\equiv g^{\frac{p-1}n}\mod p
\]

所以我们直接用\(g\)代替\(\omega_n\)做FFT就好了。

做IFFT时就用\(g\)的逆元做就好了。

还是别忘记乘\(\frac 1 N\)。

掌握了FFT，NTT还是很简单的。

void ntt(ll *a,int type)
{
    for(int i=0;i<lim;i++)
        if(i<rev[i])
            swap(a[i],a[rev[i]]);
    for(int mid=1;mid<lim;mid<<=1)
    {
        ll wn=qp(type?g:gi,(mod-1)/(mid<<1));
        for(int i=0;i<lim;i+=(mid<<1))
        {
            ll w=1;
            for(int j=0;j<mid;j++,w=w*wn%mod)
            {
                ll x=a[i+j],y=w*a[i+j+mid]%mod;
                a[i+j]=(x+y)%mod;
                a[i+j+mid]=(x-y+mod)%mod;
            }
        }
    }
    if(!type)
    {
        ll inv=qp(lim,mod-2);
        for(int i=0;i<lim;i++)
            a[i]=(a[i]*inv)%mod;
    }
}