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 ]
NTT
所以我们直接用(g)代替(\omega_n)做FFT就好了。
做IFFT时就用(g)的逆元做就好了。
还是别忘记乘(\frac 1 N)。
掌握了FFT，NTT还是很简单的。
void ntt(ll *a,int type)
{
for(int i=0;i
Original: https://www.cnblogs.com/29taorz/p/15719612.html
Author: T_X蒻
Title: NTT 快速数论变换
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/643434/
转载文章受原作者版权保护。转载请注明原作者出处！