wuvin
Always take risks!
Toggle navigation
wuvin
主页
实验室的搬砖生活
机器学习
公开的学术内容
公开的其他内容
About Me
归档
标签
友情链接
ZYQN
ihopenot
enigma_aw
hzwer
杨宗翰
myy FFT
? FFT ?
2017-03-19 20:29:54
401
0
0
wuvin
? FFT ?
最近学了myy FFT，myy好神啊！ORZORZORZ 先截一张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)$ 因为 $C(( nr, mi)) =( Ar - Bi , Ai + Br )$ $C(( nr, -mi ))=( Ar+Bi , -Ai + Br )$ 所以可以通过最终结果推出Ar Ai Br Bi就可以求得A和B了
上一篇:
BZOJ 2090 [Poi2010] Monotonicity 2
下一篇:
Splay启发式合并
0
赞
401 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
文档导航
wuvin
没有帐号? 立即注册