NTT

由于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。

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

NTT

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

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

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

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

void ntt(ll *a,int type)
{
	for(int i=0;i