【Battle】
Enzo2
posted @ 2015年6月22日 22:11
in 未分类
, 357 阅读
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]里面。