FFT

大佬博客
基本的东西在这里面都比较全，解释一下一些可能的疑点：

  1. 其实单位根还有一条比较好用的性质——$w^x_n*w^y_n=w^{x+y}_n$ ,关于这一结论可以先转为复数形式，相乘并用三角函数恒等变换化简得到
  2. 最开始存系数的数组在跑完第一遍FFT以后，存的就相当于那$n$个$x$对应的$y$了
  3. 之所以每一层出来出来的$w^k_n$所属的$n$会不一样，其实是因为$w^{2k}n=w^k{\frac{n}{2}}$ ，类似于快速幂的思想，按下标奇偶分着算到最后凑出来的数将会是对的
  4. 附加的e~，感觉上来说，FT和DFT唯一的关系就在于FT对于正弦波向其出现程度的转化和出现程度逆转化回正弦波就如同DFT中对多项式的系数与点值表示法的相互转换，而FFT则是利用了一些特殊性质进行二分优化

蝶形变换

我觉得还是精讲一下蝶形变换吧，毕竟这个玩意还是有一点点难想。

蝶形变换，就是为了解决二进制反转后序号的问题，即把每一个数转换成二进制形态，再完全反转过来，按得到的数值重排。

其实不要把蝶形变换看的很难就导致想到一些稀奇古怪的做法，事实上，他利用的更多是一种递推。

我们得到一个下标 $a$ 所在位置 $x$ ，那么如果我想用它来得到 $a<<1$ 和 $(a<<1)+1$ 的位置该怎么做？

类似 $dp$ 的递推，思考一下假设是正常的未变换形态，那么我们可以得到就是$x<<1$ 和 $(x<<1)+1$，毕竟就相当于左移一位了嘛，只不过奇数需要在最后一位补上一个 $1$ 。

那相对应的，变换后的理应满足是右移一位，也就是之前的反向，而奇数就是在最高位添加一个 $1$ 。

这样一来，我们就有$\Theta(n)$求出蝶形变换的方法了。

这名字听着倒还挺美