标签 - FFT

? FFT ?    2017-03-19 20:29:54    338    0    0

最近学了myy FFT,myy好神啊!ORZORZORZ

先截一张UOJ提交记录

UOJ

时间 写法
3998ms 递归FFT
722ms 非递归FFT,手写虚数
697ms 记忆化单位根
600ms 加入快速读入
510ms 两次的 myy FFT
477ms 手动优化核心部分代码减少变量

(真不知道jcvb的200ms的FFT是怎么做到的)(人帅常数大)
myy FFT就是把两个FFT装入一个FFT中,最后分离出来。

这样可以减少一半的FFT次数。

假设原有多项式为A和B。C为一个即将FFT的虚数数组

Ci.r=Ai Ci.i=Bi (i为虚数部,r为实数部) (x,y)表示实数部为x,虚数系数为y
F(x) 表示将数字带入多项式的结果
x是单位根的某一个次方

一定带入过C((nr,mi))C((nr,mi))

(nr,mi)(nr,mi)无论多少次方 都满足 实数部相同 虚数部相反


A((nr,mi))=(Ar,Ai)
A((nr,mi))=(Ar,Ai)
B((nr,mi))=(Br,Bi)
B((nr,mi))=(Br,Bi)B((nr,mi))=(Br,Bi)
因为
C((nr,mi))=(ArBi,Ai+Br)C((nr,mi))=(ArBi,Ai+Br)
C((nr,mi))=(Ar+Bi,Ai+Br)C((nr,mi))=(Ar+Bi,Ai+Br)
所以可以通过最终结果推出Ar Ai Br Bi就可以求得A和B了

? FFT ?    2017-03-19 20:06:26    338    0    0

首先回顾了FFT的性质与原理,发现如果单位根w满足一下条件就可以达到FFT的效果。wn=1,wn2=1

所以根据如上理论,NTT的要求w必须是模意义下的原根,这样才可以满足以上要求。而模数mod必须满足mod=1,2,4,p,2p,pn (p是奇质数)。

原根的判定

在模mod的意义下xϕ(mod)1,并且不存在比ϕ(mod)更小的次方满足等于1的条件。