【JUNE】
【总结】算法相关

【Battle】

Enzo2 posted @ 2015年6月22日 22:11 in 未分类 , 383 阅读

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]里面。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter