分治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了。具体来说每次考虑让左边的加一条边，正好落在右边即可。