分治FFT的正确姿势

在做【UNR #4】校园闲逛的时候,发现可以分治FFT,就试着冲了一下。结果之后很久没写出来。orz了skyh大神的代码之后才搞出来,尝试总结一下

首先这道题怎么整:一种非正解但是能过的做法就是,考虑直接分治FFT,则f_{x,y,i}f_{x,z,j},f_{z,y,i-j}拼出来。用分治优化。

问题1:这个函数是自己卷自己,怎么做:

https://prutekoi.github.io/post/wo-juan-wo-zi-ji/

这道题的分治较特殊先不表。对于一半的形如自己卷自己的分治FFT,可以考虑对左端点分类讨论。如果左端点是0,直接左边自己卷一下就可以对右边产生贡献。如果不是0,考虑对右边的贡献:[l,mid]一段与[0,r-l+1]一段卷起来。这里有一个细节:事实上此时一个位置会被算两次。所以要乘一下

问题2:本题一条路径只能被统计一次,怎么做:

先介绍一下大神的做法:当l=0时,先递归计算,之后计算一条路径和一条路的拼接。要求拼起来之后贡献到右边。当l \neq 0时,计算路径和路径的拼接。要求一条路径比l长,一条短。注意到此时右边已经计算完毕,不递归直接返回。

由于一条路径一定可以拆开,使得一段大于等于一半,且大于的一半是极短的(即去掉一条边会小于),所以是不漏的。由于一旦一条路径可以被拆开,立即被计算,所以是不重的。

大神的做法太神了,所以记一下正常做法:实际上不需要用自己卷自己的高妙技巧,我们可以考虑每次都是只加一条边上去。这样就可以直接一般通过分治FFT了。具体来说每次考虑让左边的加一条边,正好落在右边即可。

发表评论

电子邮件地址不会被公开。必填项已用 * 标注