wuvin

最近学了myy FFT，myy好神啊！ORZORZORZ

先截一张UOJ提交记录

（真不知道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)$
因为
$C(( nr, mi)) =( Ar - Bi , Ai + Br )$
$C(( nr, -mi ))=( Ar+Bi , -Ai + Br )$
所以可以通过最终结果推出Ar Ai Br Bi就可以求得A和B了

首先回顾了FFT的性质与原理，发现如果单位根w满足一下条件就可以达到FFT的效果。$w^n=1,w^{\frac{n}{2}}=-1$。

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

原根的判定

在模mod的意义下$x^{\phi(mod)}\equiv 1$，并且不存在比$\phi(mod)$更小的次方满足等于1的条件。