安塔的FFT学习笔记

# 前言 [总前言](https://www.luogu.org/blog/Atalod/learning-note-pre) 别人学东西：往死里学，一学学一天，学会再干其他事情。 安塔学东西：一年前看一遍，哦，理解了，一个月后再看一遍，哦，理解了，一周后再看一遍，好的可以开始写了，WA，WA，RE，WA，再看一遍，WA+RE，按着题解看一遍，A了三个点，A了五个点，终于A了，诶嘿我会了，一周后，WA。 最后：虽然安塔说说是可以一个晚上学一个算法，实际时间加起来比谁都多。 # 单位根 这里假设你已经看过其他其他dalao的博客，阅览过他们精美的复数图案了。因为安塔懒，不想贴QwQ。 令$\omega_n^k$表示第k个n次单位根（LaTeX代码`\omega_n^k`）。 单位根的性质： + $\omega_{2n}^{2k}=\omega_n^k$ + $(\omega_n^{k_1})^{k_2} = \omega_n^{k_1\times k_2}$ + $\omega_n^{n+k} = \omega_n^k$ + $\omega_n^{k} = -\omega_n^{k-n/2}$（当n为偶数时） # FFT FFT的目标：将多项式快速转化为点值表达式。 对于一个n次多项式$F(x)$，将$\omega_n^k$代入，得到n个点值表达式。 即，$F(x)$的点值表达式为$\{(w_n^i,F(w_n^i))|1\leq i \leq n\}$ 如果暴力计算的话是肯定$\Theta(n^2)$的，所以就要考虑将某个计算结果复用一下。 按着几个基本思路考虑，似乎没有啥可以用来贪心的性质（~~不是最优化问题你贪个毛线~~），递推也举步维艰，那就分治好了QwQ。 一般而言，对于这种没有很强的时序性（即各项平等）的东西很难搞递推，要么贪心出一个时序性，要么构造一个时序线出来，要么直接搞分治（性感理解一下：将一个糊状的东西切成两半比将一个糊状的东西搞成线型的简单多了QwQ） 分治的三个基本步骤：分、治、合。在构造分治方案的时候，突破口可以选在如何将大问题分解为小问题上，即从**分**的一步开始考虑。因为治一般没有任何问题，合的一步严重依赖于分的方式。 注意：由于我们已经决定采用分治法解题了，以下都假设n+1为偶数（考虑0次项qwq）。 考虑一个很显然的方案：将原多项式中次数大于n/2的项分为一类，小于等于n/2的项分为一类。即： $$F(x) = F'(x)+x^{n/2+1}\times F''(x)$$ 好的，分完啦。接下来就假设我们治完了，考虑合的步骤。 这里我们一分就分出了两个规模为$n/2$的子问题，即$T(n)=2T(n/2)+\Theta(\text{合})$，如果$\Theta(\text{合})$的复杂度为$\Theta(n^2)$的话，我们就还不如直接暴力搞搞。而且我们目前来看也不需要用到$\Theta(nlogn)$数据结构或者$\Theta(nlog^2n)$毒瘤数据结构，所以$\Theta(\text{合})$的复杂度最有可能为$\Theta(n)$（安塔式乱分析） 于是我们就悲催地发现，对于一个单位根及其对应的点值，要在均摊$\Theta(1)$的时间内搞定。 对于一个单位根$\omega_n^k$，根据上面的式子，可以推得： $$F(\omega_n^k)=F'(\omega_n^k)+(\omega_n^k)^{n/2+1}\times F''(\omega_n^k)$$ ~~一口老血~~ 场面突然变得十分尴尬。因为我们只解决了$F'(x)$的点值表达，即，在合的步骤我们可以在均摊$\Theta(1)$的时间内得知$F'(\omega_{n/2}^k)$，但是，我们要求的是$F'(\omega_n^k)$。哦豁，完蛋。 正在一筹莫展之际，我们发现$\omega_{2n}^{2k}=\omega_n^k$，即若k为偶数，$\omega_{n}^{k}=\omega_{n/2}^{k/2}$。 接下来啥废话都不用说了，拍式子吧。将原式按照次数的奇偶性分为两类，得： $$F(x) = F'(x^2)+x\times F''(x^2)$$ 对于一个单位根$\omega_n^k$，我们往里代代，得到： $$F(\omega_n^k)=F'((\omega_n^k)^2)+\omega_n^k\times F''((\omega_n^{k})^2)$$ 顺手化一下，就能得到这么一个漂亮的式子： $$F(\omega_n^k) = F'(\omega_{n/2}^k)+\omega_n^k\times F''(\omega_{n/2}^k)$$ > 要什么漂亮的妹子，我们有漂亮的式子就够了 ——我也不知道是谁说的 # FFT的逆变换（TFF，快速叶里傅变换） 于是，我们就能够在$\Theta(n\log n)$的时间内完成多项式->点值表达的过程。但是，又不能输出点值表达，还得转回来是吧。 （别管那个TFF，我自己取的名字，搜TFF啥都搜不到） 形式化地说，我们要求出一个$G(x)$，满足： $$G(x)=\{(i,G(\omega_n^i))|1\leq i\leq n\}$$ 其中$\{(i,G(\omega_n^i))|1\leq i\leq n\}$已给定。 由于我们上面搞出了一个漂亮的FFT，我们必然会搞到一个漂亮的TFF（暴论），所以，我们将这个点值表达式看做一个多项式，即令： $$G'(x)=\sum\limits_{i=0}^{n-1}(G(\omega_n^i)\times x^i)$$ 然后就是玄幻的事情了——我们将随便什么$\omega_n^k$代进去（没错我们今天就是要和单位根过不去）： $$G'(\omega_n^k)=\sum\limits_{i=0}^{n-1}(G(\omega_n^i)\times \omega_n^{k\times i})$$ 然后就是吐血化简流程QwQ。 $$G'(\omega_n^k)=\sum\limits_{i=0}^{n-1}((\sum\limits_{j=0}^{n-1}a_j\times\omega_n^{j\times i})\times \omega_n^{k\times i})$$ $$G'(\omega_n^k)=\sum\limits_{i=0}^{n-1}(\sum\limits_{j=0}^{n-1}a_j\times\omega_n^{(j+k)\times i})$$ $$G'(\omega_n^k)=\sum\limits_{i=0}^{n-1}(a_i\times\sum\limits_{j=0}^{n-1}\omega_n^{(i+k)\times j})$$ 也就是说，$G'(\omega_n^k)$的值为第i项系数乘以$\sum\limits_{j=0}^{n-1}\omega_n^{(i+k)\times j}$的和。 当$i=n-k$时，显然$\sum\limits_{j=0}^{n-1}\omega_n^{(i+k)\times j}=\sum\limits_{j=0}^{n-1}1=n$。 否则，应用等比数列公式： $$\sum\limits_{j=0}^{n-1}\omega_n^{(i+k)\times j}=\sum\limits_{j=0}^{n-1}\omega_n^{x\times j}=\sum\limits_{j=0}^{n-1}(\omega_n^x)^j=\frac{1\times(1-(w_n^x)^n)}{1-w_n^x}=\frac{1\times(1-1)}{1-w_n^x}=0$$ 我们就可以发现一个很漂亮的东西： $$G'(\omega_n^k)=\sum\limits_{i=0}^{n-1}(a_i\times\sum\limits_{j=0}^{n-1}\omega_n^{(i+k)\times j})=n\times a_{n-k}$$ 也就是说，我们把求出来的点值表达式转成多项式，再求它的点值表达式，则答案的第$i$项就是第二个点值表达式的第$n-i$项除以n。 # 进一步分析 如果淡化了数学公式和$\omega_n^k$一类的细节，FFT是怎么样的呢？ ~~会变成TT~~ 如果追踪某一个项的话，可以看到其次数的变化情况就是一个快速幂。 如果从整体考虑，某一层FFT合并时的两个数组都是只有**一半值**代入**一半项**的结果数组。合并的时候，我们只能合并一种残缺的东西。如果我们知道全部的值代入一半的项的结果的话，就可以简单地按整体快速幂一样的方式处理。如果我们知道一半的值代入全部的项的结果的话，就可以直接合并。如果我们只知道一半的值和一半的项的话，就没有足够的信息完成合并。 如果每次分治只对项分治或只对值分治的话，另一个东西就是$\Theta(N)$而不是$\Theta(n)$，总时间复杂度就是$\Theta(n^2)$的级别。 一个解决方案是，每次进行四重递归，解决四个子问题，那样的时间复杂度是： $$T(n)=4\times T(n/2)+\Theta(n)$$ 随手画颗递归树，我们就能发现 $$T(n)=\sum\limits_{i=0}^{\log_2n}2^i\times n=\Theta(n^2)$$ 如果处处$\Theta(n^2)$的话，我们还不如暴力。幸运的是，我们有单位根这种东西。单位根的性质保证了$\omega_n^n=1$，即我们的两个数组都不是**一半值**，而是**全部值**。简单地将数组复制一份，我们就能够得到全部值。 所以，先使用分治的方法，遇到了分治只能分治出一半值的困难，然后再引入单位根解决是一个比较合理的提出FFT的顺序，也是一个比较合理的理解FFT的顺序。（//TODO） **FFT先是分治，然后才是单位根。** # 总结 应该还是有别的博客没有的东西的QwQ。 （写完博客感觉缺了点啥，第二天才发现是代码没贴，算了代码到其他博客随便一扒拉就有的qwq） # 拓展-NTT FTT全是复数运算，常数大，容易被卡精，究其原因，是因为我们把整数的问题变成了浮点数的问题。 那有没有什么方法可以只在整数里面解决问题呢？ 从上，我们得知我们必须得选择一个$x_n^n=1$的神奇数x，并且，我们显然不能选择1。但是，在整数里面，并没有那个神奇的数，因为如果我们不断的乘下去，它必定会越来越远离0。所以，我们必须得取个模。 取模相当于人为造出了一个环。 回顾我们已有的知识，我们知道$a^{p-1}=1\mod p$，所以a是p的一个原根。我们发现，右边刚好是个1。所以，我们就可以这么定义一个东西： $$g_n^k=g^{k\times\frac{p-1}{n}} \mod p$$ 然后用它愉快地代掉$\omega_n^k$，于是，我们就……等等，如果`p-1`不是`n`的倍数呢？ 想用逆元？但是n在$mod\space p-1$意义下似乎没啥逆元的样子。 由于n是$2^k$的形式，所以p必须是$r\times2^k+1$的形式。然后就是找模数了，这个似乎只能暴力枚举判断。而且，找出来的模数不能太小，也不能爆int。找出来的里面`998244353`最为典型。 接下来……要我再把FTT的东西再贴一遍吗？