fft 变换_积分区间怎么变换

FFT（快速傅里叶变换）　　介绍　　快速傅里叶变换（Fast Fourier Transform），简称 FFT，在算法竞赛上，我们通常使用 FFT 去解决多项式相乘的问题。　　如右，这是一个长度为
的
n-1 次多项式
$F(x)=\displaystyle\sum_{i=0}^{n-1} a_ix^i$ ，其中
a_i 被称为多项式第
项的系数，由此我们可知，一个
n-1 次多项式
F(x) 可以通过一组长度为
的系数序列所确定，我们称作系数表示法，例如上式
可以被系数表示法表示为
$[a_0,a_1,a_2,\cdots,a_{n-1}]$ ，为了方便之后的描述，我们不妨记
F[x] 表示
多项式第
项的系数。　　根据初中知识，对于两个多项式
F,G ，设长度分别为
n,m ，那么两者相乘的第三多项式
一定有
$H[i]=\displaystyle\sum_{j+k=i}F[j]G[k]$ ，形如这样的求和我们称为卷积，简写为
F*G=H ，由于我们求和下标做的是加法运算（即
j+k=i 这一部分），因此我们称这类卷积为加法卷积（多项式的乘法）。不过，直接暴力遍历
F,G 去求它俩的卷积太慢了，最优情况下也需要
O(nm) 的时间复杂度。　　而且，单是系数表示法也不好优化，因此我们需要引入另一种多项式表示法：点值表示法。　　点值表示法　　对于一个多项式
，我们可以代入一个
，它可以返回一个
，如
y=f(x) ，不妨将多项式放到直角坐标系上来看，那么这些
x,y 形成了若干个点对
，同时我们可以由
个不同的点对确定出一个唯一
n-1 次多项式，确定的方法就是解方程来求出多项式所对应的系数，如下　　
$\begin{cases} a_0+a_1x_1+a_2x_1^2+\cdots +a_{n-1}x_1^{n-1}=y_1\\ a_0+a_1x_2+a_2x_2^2+\cdots +a_{n-1}x_2^{n-1}=y_2\\ a_0+a_1x_3+a_2x_3^2+\cdots +a_{n-1}x_3^{n-1}=y_3\\ \cdots\\ a_0+a_1x_n+a_2x_n^2+\cdots +a_{n-1}x_n^{n-1}=y_n\\ \end{cases}\\$ 我们由
个点值确定出一个多项式，这种方式我们称作为点值表示法。　　点值表示法有一个好处就是可以快速处理两个多项式的卷积，如下：　　对于一个长度为
的多项式
，和一个长度为
的多项式
，现在有平面上
n+m-2 个横坐标
x_i 。　　我们用
$(x_1,F(x_1)),(x_2,F(x_2)),(x_3,F(x_3)),\cdots,(x_{n+m-2},F(x_{n+m-2}))$ 来表示多项式
。　　用
$(x_1,G(x_1)),(x_2,G(x_2)),(x_3,G(x_3)),\cdots,(x_{n+m-2},G(x_{n+m-2}))$ 来表示多项式
。　　那么两者的卷积
，可以用点值表达式这样表达：
$(x_1,F(x_1)\cdot G(x_1)),(x_2,F(x_2)\cdot G(x_2)),(x_3,F(x_3)\cdot G(x_3))\cdots(x_{n+m-2},F(x_{n+m-2})\cdot G(x_{n+m-2}))$ 　　这样我们求出
的点值表达式的时间复杂度就是
O(n+m) 。　　当然，我们最终用到的还是系数表示法，若是直接使用拉格朗日插值法去求解方程的话，时间复杂度会变成
O(n^2) ，和直接系数表达做无异区别。　　当然，有些题目是不会直接给你两个多项式的点值表达式再叫你去求解它们的卷积，因此我们还需考虑如何将系数表达式转换成为点值表达式，直接做的话还是
O(n^2) ，甚至不如直接系数表达式暴力去做，但是这种方法和直接暴力做不同点在于，它可以被优化，具体怎么优化，我们后面再讲。　　单位根　　复数我们早在高中时期就学了，这里也就不详细阐述了，具体看复数（高中数学三）（当然也不是很具体），接下来我们要介绍的是单位根。　　在复平面上给定一个圆心为原点的单位圆，不妨将其分成
等份，这种分圆形成的
个点我们称为
次单位根。

　　规定
$\omega_n^k$ 表示将圆分成
份后第
份所表示的复数（
从
开始标号），易得
$\arg\omega_n^k=\dfrac{2k\pi}{n}$ ，
$\omega_n^k=\cos\left(\dfrac{2k\pi}{n}\right)+\sin\left(\dfrac{2k\pi}{n}\right)i$ 。　　单位根有以下几种性质：互异性，
$\forall i\not = j$ ，有
$\omega_n^i\not = \omega_n^{j}$ ，
个单位根对应的是
个不同的点。循环性，即
$\omega_n^k=\omega_n^{k+tn}(t\in\mathbb{N})$ 。
$\omega_{2n}^{2k}=\omega_n^k$ ，分成
份取
份，等价于分成
份取
份。当
$2\mid n$ 时，有
$\omega_n^{k+\frac{n}{2}}=-\omega_n^k$ ，相当于一个向量旋转了
180 度。对称性，有
$\sum_{i=0}^n \omega_n^i=0$ 。　　同时根据复数相乘法则，我们能够得到
$(\omega_n^k)^c=\omega_n^{kc}$ 。　　如果
$\gcd(n,k)=1$ ，那么称
$\omega_n^k$ 为本原单位根，本原单位根在我们之后的 NTT 会用到。　　FFT（快速傅里叶变换）　　FFT 解决的是快速将多项式系数表达式转换为点值表达式。　　对于长度为
的多项式
，如果我们随机选出
个点，那么时间复杂度还是
O(n^2) ，考虑怎么选出
个点才能快速转换成点值表达式，上文我们介绍的
次单位根就刚好可以快速转换，不妨取复数域上的
个点
$\omega_n^0,\omega_n^1,\omega_n^2,\cdots,\omega_n^{n-1}$ ，现在我们的问题就是如何快速求出
。　　为了方便计算，我们通常强制把
转换称为一个大于等于
的最小
的幂，即
$n\leftarrow 2^{\lceil\log_2 n\rceil}$ ，多余的项我们用系数
补充。　　现在我们将多项式
按照指数分为两类：
$F(x)=(a_0+a_2x^2+\cdots a_{n-2}x^{n-2})+(a_1x+a_3x^3+\cdots+a_{n-1}x^{n-1})$ 。　　不妨设
$F_0(x)=a_0+a_2x+\cdots+a_{n-2}x^{\frac{n-2}{2}}$ ，
$F_1(x)=a_1+a_3x+\cdots+a_{n-1}x^{\frac{n-2}{2}}$ 。　　那么有
，得到
$F(\omega_n^k)=F_0(\omega_n^{2k})+\omega_n^kF_1(\omega_n^{2k})$ ，看到这个，再联想到上面我们说到的单位根的性质，似乎就很好做了，但是先别着急，为了更好优化此过程，我们还要对
的值域分类讨论。　　当
$k\in [0,\dfrac{n}{2})$ 时，有　　
$\begin{aligned}F(\omega_n^k)&=F_0(\omega_n^{2k})+\omega_n^kF_1(\omega_n^{2k}) \\&=F_0(\omega_{n/2}^k)+\omega_n^k F_1(\omega_{n/2}^k) \end{aligned}\\$ 　　当
$k\in[\dfrac{n}{2},n)$ 时，记
$k^{'}=k-\dfrac{n}{2}$ ，那么有　　
$\begin{aligned} F(\omega_n^k)&=F(\omega_n^{k^{'}+n/2})\\ &=F_0(\omega_n^{2k^{'}+n})+\omega^{k^{'}+n/2}_nF_1(\omega_n^{2k^{'}+n})\\ &=F_0(\omega_{n/2}^{k^{'}+n/2})-\omega_n^{k^{'}}F_1(\omega_{n/2}^{k^{'}+n/2})\\ &=F_0(\omega_{n/2}^{k^{'}})-\omega_n^{k^{'}}F_1(\omega_{n/2}^{k^{'}}) \end{aligned}\\$ 我们发现
$k\in[0,\dfrac{n}{2})$ 和
$k\in[\dfrac{n}{2},n)$ 这两种情况最终得到的式子是相似的，那么也就是说，我们可以通过前
$\dfrac{n}{2}$ 个值来求出后
$\dfrac{n}{2}$ 个值，我们按照这样的方式不断分治下去，最终就能还原整个
$F(\omega_n^k)$ 了，递归次数最多不超过
$\log n$ ，每次合并时间复杂度不会超过
O(n) ，因此总时间复杂度为
$O(n\log n)$ ，我们能很容易的写出如下代码：　　但是我们的递归同样需要占一些空间，因此空间复杂度也是
$O(n\log n)$ ，而且递归常数大，很容易被卡，我们希望能够直接递推求出 FFT，这时候就需要我们的蝴蝶变换优化了。　　蝴蝶操作优化　　我们不妨以一个简单的例子来模拟该递归过程，现在有
n=8 ，那么有　　第
层：
$\{a_0,a_1,a_2,a_3,a_4,a_5,a_6,a_7\}$ 。　　第
层：
$\{a_0,a_2,a_4,a_6\},\{a_1,a_3,a_5,a_7\}$ 。　　第
层：
$\{a_0,a_4\},\{a_2,a_6\},\{a_1,a_5\},\{a_3,a_7\}$ 。　　第
层：
$\{a_0\},\{a_4\},\{a_2\},\{a_6\},\{a_1\},\{a_5\},\{a_3\},\{a_7\}$ 。　　我们现在需要一层一层从第
层向上递归求解。　　我们现在要求的就是对于每一层，
序列下标的排列，我们记
rev[i] 表示最后一层第
个数在原数组的位置。　　由于我们是按照下标的奇偶性进行分类，不难想到
rev[i] 的求解和二进制有关，我们将上面模拟的结果换成下标并二进制表达可以得到：　　第
层：
$\{000,001,010,011,100,101,110,111\}$ 。　　第
层：
$\{000,010,100,110\},\{001,011,101,111\}$ 。　　第
层：
$\{000,100\},\{010,110\},\{001,101\},\{011,111\}$ 。　　第
层：
$\{000\},\{100\},\{010\},\{110\},\{001\},\{101\},\{011\},\{111\}$ 。　　按照二进制的做法我们可以看出第
层到第
i+1 层的分类是按照从二进制位末尾第
为是否为
分的，更近一步的，有第
层被分成一组的集合中的数二进制最后
位都是相同的，我们称之为
分类方式。　　上面的是按照末尾是否为
分类的，假如我们按照从首位开始第
位是否为
分类，那么得到的序列和原序列相同，更近一步的，有第
层被分成一组的集合中的数二进制前面
位都是相同的，我们称之为
分类方式。　　显然的，将第
层
分类方式得到的集合中每一个数翻转一下（比如
1010 翻转得到
0101 ），那么得到的集合一定满足
分类方式，而我们已知
分类方式最终得到的结果是好求的，因此我们可以翻转将
类变成
类，那么有
rev[i] 为
二进制翻转后得到的结果，现在问题就是怎么快速翻转
，你当然可以
$O(n\log n)$ 翻转，但是我们有更简单的方法。　　假设我们现在要翻转
，我们将它右移一位得到
，我们是已知它的翻转是什么（因为我们是从
到
递推求出），即
，之前右移一位导致我们在末尾多出了一个
，我们只需在右移一位即可去掉这个
，得到
，之前我们右移一位导致我们最后一位的
丢失了，而现在它应该被翻转到第
位，因此我们需要加上这个
，得到
，结果刚好是原串
的翻转。　　因此我们可以得到如下代码：　　当然我们需要转换的是
，也就是将
$a_i\gets a_{rev[i]}$ ，我们当然不需要新建一个数组来求，我们可以这样做：对于
的
交换
$a_i,a_{rev[i]}$ ，这样刚好是
$a_i\gets a_{rev[i]}$ ，
$a_{rev[i]}\gets a_{rev[rev[i]]}$ ，即
$a_{rev[i]}\gets a_{i}$ ，而对于
的
我们根本不需要翻转，因此这样做是正确的。　　我们现在唯一的问题就是如何将当前序列和并得到下一个序列，这个很简单，我们直接按照递归合并方式合并即可，综上，我们可以得出递归求解 FFT 的代码了。　　时间复杂度
$O(n\log n)$ 。　　而在快速傅里叶变换之后，我们要做的就是将
的点值表达式乘上
的点值表达式，得到
的点值表达式，再转换到系数表达式。　　IFFT（快速傅里叶逆变换）　　IFFT 解决的是快速将多项式点值表达式转换为系数表达式。　　我们目前已知多项式
的点值表达式，即我们现在有这么几个点
$(x_i,y_i)=(\omega_n^i,H(\omega_n^i))$ ，我们设
h_i 表示
的系数表达式，即
$H(x)=\displaystyle \sum_{i=0}^{n-1} h_ix^i$ ，设向量
$(c_0,c_1,\cdots,c_{n-1})$ 满足　　
$c_k=\sum_{i=0}^{n-1}y_i(\omega_n^{-k})^i\\$ 那么有：　　
$\begin{aligned} c_k&=\sum_{i=0}^{n-1}y_i(\omega_n^{-k})^i\\ &=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}h_j(\omega_n^{i})^j(\omega_n^{-k})^i\\ &=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}h_j(\omega_n^{i(j-k)})\\ &=\sum_{j=0}^{n-1}h_j\sum_{i=0}^{n-1}\omega_n^{i(j-k)} \end{aligned} \\$ 我们不妨对
$\displaystyle\sum_{i=0}^{n-1}\omega_n^{i(j-k)}$ 进行分类讨论：　　当
j=k 时，显然该式子等于
。　　当
$j\not = k$ 时，根据单位根的性质可以得到该式恒等于
。　　那么得到
，因此得到
$h_k=\dfrac{c_k}{n}$ ，因此我们只需快速求出
c_k 就能求出
h_k 了。　　我们不妨令
$C(x)=\displaystyle\sum_{i=0}^{n-1}y_ix^i$ ，显然这是一个多项式的系数表达式，对于每个
，我们将
$\omega_n^{-k}$ 依次代入多项式即可求值，事实上就是将
的系数表达式转换为点值表达式，我们 FFT 转换的点值是
$\omega_n^{k}$ ，而这里我们要转换的点值为
$\omega_n^{-k}$ ，是不是非常相似，它们俩都是在单位圆上的，只是两者旋转方向不同，因此我们只需对
做一遍 FFT，然后翻转得到的序列即可。　　需要注意的是，由于
$\omega_n^0=\omega_n^n$ ，因此我们翻转的区间是
[1,n) 而非
[0,n) ，时间复杂度
$O(n\log n)$ 。　　因此总时间复杂度为
$O(n\log n)$ 。　　下面给出例题【模板】多项式乘法（FFT）的完整代码　　当然，IFFT 有另一种更简便的写法，我们 FFT 算的是
$\omega_n^i$ ，而我们 IFFT 需要算的是
$\omega_n^{-i}$ ，只是旋转方向不同，所以我们在原 FFT 的基础上改变
$\omega$ 的旋转方向即可。

fft 变换_积分区间怎么变换

相关推荐