FFT

理解的前提是背诵。

只用记住就可以了

理解FFT的关键有几点：点值表达，插值运算；N次单位复数根；蝶形运算：

Code：BZOJ 3527: [Zjoi2014]力

而理解NFT的关键是N次单位复数根上的折半引理这一性质：

Code: NFT的简单实现

一般的NFT对模数P是有要求的，一般满足P=A*2^X+1的形式(如167772161, 998244353, 1004535809)。
但现在已经不止于这些质数，如P=10^9+7也逐渐出现在国外的比赛中。(所以已经不能通过模数来判断这道题应不应该使用FFT)
由于进行多项式乘法后每一项必定小于P*P*N，那么只要取几个可以使用NFT的模数分别计算，用CRT合并出结果即可。
那么上面的三个质数就可以应付大多数情况了。

Code : 合并的简单实现

几种题目类型

按时间分治计算FFT

再前面的文章有提及。

生成元

使用生成元可以把乘积化成加法，从而达到卷积的形式。 UOJ#86.BZOJ3992

循环卷积

如果两个N次多项式相乘，但次数界只设为N，使用FFT会有什么样的效果? 一个原本存在的项F[x](x>N),会被累加到F[x%N]里面。