FFT
作用：快速求两个多项式的乘积/卷积
文章目录
FFT前置知识复数（Complex）单位根离散傅立叶变换（Discrete Fourier Transform , DFT）快速傅立叶变换(Fast Fourier transform , FFT)**离散傅立叶逆变换（Inverse Discrete Fourier Transform , IDFT）**快速傅立叶逆变换（Inverse Fast Fourier transform,IFFT）蝴蝶变换例题前置知识
多项式乘法（点表示法）：用任意n + 1个不同点，均可确定为一个n次多项式。
好处：如果有两个多项式A,B:
A(x)=a0+a1x1+a2x2+a3x3+....B(x)=b0+b1x1+b2x2+b3x3+....多项式A点表示法为(x1,A(x1)),(x2,A(x2),(x3,A(x3)))...多项式B点表示法为(x1,B(x1)),(x2,B(x2),(x3,B(x3)))...那么C可以表示为A(xi)∗B(xi);多项式C点表示法为(x1,C(x1)),(x2,C(x2),(x3,C(x3)))...（o(n)）A(x) = a_0 + {a_1}x^1+ {a_2}x^2+ {a_3}x^3+....\\ B(x) = b_0 + {b_1}x^1+ {b_2}x^2+ {b_3}x^3+....\\ 多项式A点表示法为(x_1 , A(x_1))~,~(x_2 , A(x_2)~,~(x_3 , A(x_3)))...\\ 多项式B点表示法为(x_1 , B(x_1))~,~(x_2 , B(x_2)~,~(x_3 , B(x_3)))...\\ 那么C可以表示为A(x_i)*B(x_i);\\ 多项式C点表示法为(x_1 , C(x_1))~,~(x_2 , C(x_2)~,~(x_3 , C(x_3)))...（o(n)） A(x)=a0+a1x1+a2x2+a3x3+....B(x)=b0+b1x1+b2x2+b3x3+....多项式A点表示法为(x1,A(x1)),(x2,A(x2),(x3,A(x3)))...多项式B点表示法为(x1,B(x1)),(x2,B(x2),(x3,B(x3)))...那么C可以表示为A(xi)∗B(xi);多项式C点表示法为(x1,C(x1)),(x2,C(x2),(x3,C(x3)))...（o(n)）
复数（Complex）
定义：1.形如a+bia+bia+bi,其中a为实部，b为虚部。
2.模长为：a2+b2\sqrt{a^2 + b ^ 2}a2+b2
3.幅角：设逆时针方向为正方向，从x正半轴到向量的转角
运算法则：（满足结合律，交换律，分配律）
1.加法满足平行四边形法则
2.乘法：几何意义：幅角相加，模长相乘
代数意义：(ac−bd)+(ad+bc)i(ac-bd) + (ad + bc)i(ac−bd)+(ad+bc)i
单位根
定义：wnkw_n^kwnk为n次单位根
性质：
wnj≠wni(∀i≠j)w_n^j \ne w_n^i(\forall_{i \ne j})wnj=wni(∀i=j)wnk=cos2kπn+sin2kπnw_n^k = cos\frac{2k\pi}{n} + sin\frac{2k\pi}{n}wnk=cosn2kπ+sinn2kπwn0=wnn=1w_n^0 = w_n^n = 1wn0=wnn=1w2n2k=wnkw_{2n}^{2k} = w_n^kw2n2k=wnk（折半引理）wnk+n2=−wnkw_n^{k + \frac{n}{2}} = -w_n^kwnk+2n=−wnk（消去引理）
离散傅立叶变换（Discrete Fourier Transform , DFT）
将系数矩阵转换为点表达式
设一个长度为n的数列d[i]d[i]d[i],这个数列的第k项为A(x)A(x)A(x)在n次单位根第k次幂处的点值。
得：
dk=∑i=0n−1ai×wnid_k = \sum_{i = 0}^{n - 1}a_i \times w_n^i dk=i=0∑n−1ai×wni
但是这样仍然是o(n2)o(n ^ 2)o(n2)，由单位根的性质，我们可得快速傅立叶变换(Fast Fourier transform , FFT)。
快速傅立叶变换(Fast Fourier transform , FFT)
对于A(x)=a0+a1x1+a2x2+a3x3+....+an−1xn−1A(x) = a_0 + {a_1}x^1+ {a_2}x^2+ {a_3}x^3+....+{a_{n - 1}x^{n -1}}A(x)=a0+a1x1+a2x2+a3x3+....+an−1xn−1
按照奇偶分组：
A(x)=a0+a1x1+a2x2+a3x3+....+an−1xn−1A(x)=(a0+a2x2+...+an−2xn−2)+x(a1+a3x2+...+an−1xn−2)以x2代x,不妨令：A1(x)=(a0+a2x+a4x2+...+an−2xn−22)A2(x)=(a1+a3x+a5x2+...+an−1xn−22)显然:A(x)=A1(x2)+xA2(x2)A(x) = a_0 + {a_1}x^1+ {a_2}x^2+ {a_3}x^3+....+{a_{n - 1}x^{n -1}} \\ A(x) = (a_0 + {a_2}x^2+...+a_{n - 2}x^{n - 2}) + x(a_1 + {a_3}x^2+...+{a_{n - 1}x^{n - 2}}) \\ \\ 以x^2代x,不妨令：\\ A_1(x) = (a_0 + a_2x+a_4x^2 + ... + a_{n - 2}x^{\frac{n - 2}{2}})\\ A_2(x) = (a_1 + a_3x+a_5x^2 + ... + a_{n - 1}x^{\frac{n - 2}{2}})\\ 显然:A(x) = A_1(x^2) + xA_2(x^2)\\ A(x)=a0+a1x1+a2x2+a3x3+....+an−1xn−1A(x)=(a0+a2x2+...+an−2xn−2)+x(a1+a3x2+...+an−1xn−2)以x2代x,不妨令：A1(x)=(a0+a2x+a4x2+...+an−2x2n−2)A2(x)=(a1+a3x+a5x2+...+an−1x2n−2)显然:A(x)=A1(x2)+xA2(x2)
根据K的大小分类讨论：n
k∈[0,n2−1]k \in [0 ~,~ \frac{n}{2}-1]k∈[0,2n−1]
A(wnk)=A1(wn2k)+wnkA2(wn2k)由折半引理得：A(wnk)=A1(wn2k)+wnkA2(wn2k)A(w_n^k) = A_1(w_n^{2k}) + {w_n^k}A_2(w_{n}^{2k}) \\ 由折半引理得： A(w_n^k) = A_1(w_{\frac{n}{2}}^{k}) + {w_n^k}A_2(w_{\frac{n}{2}}^{k})\\ A(wnk)=A1(wn2k)+wnkA2(wn2k)由折半引理得：A(wnk)=A1(w2nk)+wnkA2(w2nk)
2.k+n2∈[n2,n−1]k + \frac{n}{2} \in[\frac{n}{2} , n - 1]k+2n∈[2n,n−1]
A(wnk+n2)=A1(wn2k+n)+wnk+n2A2(wn2k+n)由消去引理得：A(wnk+n2)=A1(wn2k)−wnkA2(wn2k)A(w_n^{k + \frac{n}{2}} ) = A_1(w_n^{2k + n}) + {w_n^{k + \frac{n}{2}}}A_2(w_{n}^{2k + n})\\ 由消去引理得： A(w_n^{k + \frac{n}{2}} ) = A_1(w_{\frac{n}{2}}^{k}) - {w_n^{k}}A_2(w_{\frac{n}{2}}^{k})\\ A(wnk+2n)=A1(wn2k+n)+wnk+2nA2(wn2k+n)由消去引理得：A(wnk+2n)=A1(w2nk)−wnkA2(w2nk)
综上得： 若已知 wn2iw_{\frac{n}{2}} ^ iw2ni 那么可以快速求得A(x)A(x)A(x)点表达式。
而A1(x),A2(x)A_1(x) , A_2(x)A1(x),A2(x),为A(x)A(x)A(x)的一半规模，可以递归求解问题，那么时间复杂度为o(nlogn)o(nlogn)o(nlogn)
离散傅立叶逆变换（Inverse Discrete Fourier Transform , IDFT）
既然有了o(nlogn)o(nlogn)o(nlogn)的将系数表达式转化为点表达式的方法，那么我们自然也想用一个理想的方式将点表达式转化为系数表达式。
已知多项式A(x)=∑i=0n−1aixiA(x) = \sum_{i=0}^{n-1}a_ix^iA(x)=∑i=0n−1aixi,和其点表达式dk=∑i=0n−1ai×wnikd_k = \sum_{i = 0}^{n - 1}a_i\times w_n^{ik}dk=∑i=0n−1ai×wnik,求ai{a_i}ai.
结论：
ck=∑i=0n−1di(wn−k)ic_k = \sum_{i = 0} ^ {n - 1} d_i(w_n^{-k}) ^ i ck=i=0∑n−1di(wn−k)i
证明：
构造一多项式F(x)=d0+d1x+d2x2+...+dn−1xn−1设Ck为x=wn−k下的点表示,即ck=∑i=0n−1di(wn−k)i即多项式B(x)=d0,d1x,d2x2,...,dn−1xn−1在wn0,wn−1,....,wn−1−(n−1)的点表达式(c0,c1,c2,c3,...,cn−1)满足:ck=∑i=0n−1di(wn−k)i⇌di=∑j=0n−1aj×(wni)jck=∑i=0n−1di(wn−k)i=∑i=0n−1(∑j=0n−1aj(wni)j)(wn−k)i=∑i=0n−1(∑j=0n−1aj(wnj)i)(wn−k)i=∑i=0n−1(∑j=0n−1aj(wnj)i(wn−k)i)=∑i=0n−1∑j=0n−1aj(wnj−k)i=∑j=0n−1aj(∑i=0n−1(wnj−k)i)设S(x)=∑i=0n−1xi代入x=wnk，得：S(wnk)=1+(wnk)+(wnk)2+...+(wnk)n−1分情况讨论得：当k≠0时，两边同时×wnk,得wnkS(wnk)=wnk+(wnk)2+(wnk)3+...+(wnk)nwnks(wnk)−s(wnk)=(wnk)n−1s(wnk)=(wnk)n−1wnk−1s(wnk)=(wnn)k−1wnk−1s(wnk)=0wnk−1s(wnk)=0当k=0时，s(wnk)=1+1+...+1=n由于ck=∑j=0n−1aj(∑i=0n−1(wnj−k)i)当且仅当j=k时,ck=nakak=cknck=∑i=0n−1diwn−kiak=1n∑i=0n−1diwn−ki构造一多项式F(x) = d_0 + d_1x + d_2x^2 + ... + d_{n-1}x^{n-1} \\ 设C_k为x = w_{n}^{-k}下的点表示,即c_k = \sum_{i = 0} ^ {n - 1} d_i(w_n^{-k}) ^ i\\ 即多项式B(x) = d_0,d_1x,d_2x_2,...,d_{n - 1}x^{n - 1}在w_n^0,w_n^{-1},....,w_{n - 1} ^ {-(n - 1)}的点表达式\\(c_0,c_1,c_2,c_3,...,c_{n - 1})满足:\\ c_k = \sum_{i = 0} ^ {n - 1} d_i(w_n^{-k}) ^ i\rightleftharpoons{d_i} = \sum_{j = 0}^{n - 1}a_j \times (w_n^i) ^ j\\ c_k = \sum_{i = 0} ^ {n - 1}d_i(w_n^{-k}) ^ i\\ =\sum_{i = 0}^{n - 1}(\sum_{j = 0}^{n - 1}a_j(w_n^i)^j)(w_n^{-k})^ i\\ =\sum_{i = 0}^{n - 1}(\sum_{j = 0}^{n - 1}a_j(w_n^j)^i)(w_n^{-k})^ i\\ =\sum_{i = 0}^{n - 1}(\sum_{j = 0}^{n - 1}a_j(w_n^j)^i(w_n^{-k})^ i)\\ =\sum_{i = 0}^{n - 1}\sum_{j = 0}^{n - 1}a_j(w_n^{j - k})^i\\ =\sum_{j = 0}^{n - 1}a_j(\sum_{i = 0}^{n - 1}(w_n^{j - k})^i)\\ 设S(x) = \sum_{i = 0}^{n - 1}x_i\\ 代入x = w_n^k，得： S(w_n^k) = 1 + (w_n^k) + (w_n^k)^2+...+(w_n^k)^{n-1}\\ 分情况讨论得：\\ 当k\ne 0时，两边同时\times w_n^k,得\\ w_n^kS(w_n^k) = w_n^k + (w_n^k)^2 + (w_n^k)^3+...+(w_n^k)^{n}\\ w_n^ks(w_n^k) - s(w_n^k) = (w_n^k)^n-1\\ s(w_n^k) = \frac{(w_n^k)^n - 1}{w_n^k-1}\\ s(w_n^k) = \frac{(w_n^n)^k - 1}{w_n^k-1}\\ s(w_n^k) = \frac{0}{w_n^k - 1}\\ s(w_n^k) = 0\\ 当k = 0时，s(w_n^k) = 1 + 1 + ... + 1 = n\\ 由于c_k=\sum_{j = 0} ^ {n - 1}a_j(\sum_{i = 0}^{n - 1}(w_n^{j - k})^i)\\ 当且仅当j = k 时,c_k = na_k\\ a_k = \frac{c_k}{n}\\ c_k = \sum_{i = 0}^{n - 1}d_iw_n^{-ki}\\ a_k = \frac{1}{n}\sum_{i = 0}^{n - 1}d_iw_n^{-ki}\\ 构造一多项式F(x)=d0+d1x+d2x2+...+dn−1xn−1设Ck为x=wn−k下的点表示,即ck=i=0∑n−1di(wn−k)i即多项式B(x)=d0,d1x,d2x2,...,dn−1xn−1在wn0,wn−1,....,wn−1−(n−1)的点表达式(c0,c1,c2,c3,...,cn−1)满足:ck=i=0∑n−1di(wn−k)i⇌di=j=0∑n−1aj×(wni)jck=i=0∑n−1di(wn−k)i=i=0∑n−1(j=0∑n−1aj(wni)j)(wn−k)i=i=0∑n−1(j=0∑n−1aj(wnj)i)(wn−k)i=i=0∑n−1(j=0∑n−1aj(wnj)i(wn−k)i)=i=0∑n−1j=0∑n−1aj(wnj−k)i=j=0∑n−1aj(i=0∑n−1(wnj−k)i)设S(x)=i=0∑n−1xi代入x=wnk，得：S(wnk)=1+(wnk)+(wnk)2+...+(wnk)n−1分情况讨论得：当k=0时，两边同时×wnk,得wnkS(wnk)=wnk+(wnk)2+(wnk)3+...+(wnk)nwnks(wnk)−s(wnk)=(wnk)n−1s(wnk)=wnk−1(wnk)n−1s(wnk)=wnk−1(wnn)k−1s(wnk)=wnk−10s(wnk)=0当k=0时，s(wnk)=1+1+...+1=n由于ck=j=0∑n−1aj(i=0∑n−1(wnj−k)i)当且仅当j=k时,ck=nakak=nckck=i=0∑n−1diwn−kiak=n1i=0∑n−1diwn−ki
这个是DFT的逆变换，称为IDFT,可以通过这个式子求出多项式的系数表示法.
快速傅立叶逆变换（Inverse Fast Fourier transform,IFFT）
我们考虑的问题是如何快速求解：A(x)=∑i=0n−1bixiA(x)=\sum_{i = 0}^{n - 1}b_ix^iA(x)=∑i=0n−1bixi在wn−ki于[0,n)w_n^{-ki}于[0 , n)wn−ki于[0,n)处的点值。
从图上，我们得到：
wn−k=wnk+nw_n^{-k} = w_n^{k + n} wn−k=wnk+n
只要先算出A(X)A(X)A(X)在wnw_nwn在各个幂次的弧度，然后反过来计算就可以
ak=1n∑i=0nA(wnk)(wn−k)−1a_k=\frac{1}{n}\sum_{i = 0} ^ n A(w_n^{k})(w_n^{-k})^{-1} ak=n1i=0∑nA(wnk)(wn−k)−1
至此通过FFT,IFFT我们可以o(nlogn)o(nlogn)o(nlogn)的时间复杂度由系数表达式变成点表达式，由点表达式变成系数表达式。
蝴蝶变换
由于递归写法常数太大，我们采用神奇的蝴蝶变换，就可以让他十分高效。
第一层：a0,a1,a2,a3,a4,a5,a6,a7第二层：a0,a2,a4,,a6,a1,a3,a5,a7第三层：a0,a4,a2,a6,a1,a5,a3,a7第一层：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\\ 第一层：a0,a1,a2,a3,a4,a5,a6,a7第二层：a0,a2,a4,,a6,a1,a3,a5,a7第三层：a0,a4,a2,a6,a1,a5,a3,a7
可以发现:
原来：01234567变换：04261537实际上就是二进制位翻转原来：0~1~2~3~4~5~6~7\\ 变换：0~4~2~6~1~5~3~7\\ 实际上就是二进制位翻转 原来：01234567变换：04261537实际上就是二进制位翻转
递推式：rev[i]=(rev[i>>1]>>1)∣(i&1)<<(bit−1)递推式：rev[i] = (rev[i >> 1] >> 1)~ |~(i ~\&~1) << (bit~ - ~1) 递推式：rev[i]=(rev[i>>1]>>1)∣(i&1)<<(bit−1)
OK，到这就完全结束了。
例题
例题：多项式乘法
y总代码（注释版)：
#include <bits/stdc++.h>using namespace std;const int N = 300010;const double PI = acos(-1);int n, m;struct Complex{double x, y;//重载复数加法Complex operator+ (const Complex& t) const{return {x + t.x, y + t.y};}//重载复数减法 Complex operator- (const Complex& t) const{return {x - t.x, y - t.y};}//重载复数乘法Complex operator* (const Complex& t) const{return {x * t.x - y * t.y, x * t.y + y * t.x};}}a[N], b[N];//A，B，两个多项式//rev存的是逆转后的序列，也就是递归后的位置。//bit为最高次幂。//tot为总共多少项，补充到2的整数次项。int rev[N], bit, tot;void fft(Complex a[], int inv){//先将序列按照rev排序for (int i = 0; i < tot; i ++ )if (i < rev[i])swap(a[i], a[rev[i]]);//枚举每个分块的长度，开始迭代，一开始是1.for (int mid = 1; mid < tot; mid <<= 1){//w1是单位根，乘inv是为了方便倒着作fftauto w1 = Complex({cos(PI / mid), inv * sin(PI / mid)});//从第i块开始枚举，每次加两块for (int i = 0; i < tot; i += mid * 2){//从w0开始枚举auto wk = Complex({1, 0});//每次都++,算出x,y，存下来for (int j = 0; j < mid; j ++, wk = wk * w1){auto x = a[i + j], y = wk * a[i + j + mid];a[i + j] = x + y, a[i + j + mid] = x - y;}}}}int main(){scanf("%d%d", &n, &m);for (int i = 0; i <= n; i ++ ) scanf("%lf", &a[i].x);for (int i = 0; i <= m; i ++ ) scanf("%lf", &b[i].x);while ((1 << bit) < n + m + 1) bit ++;tot = 1 << bit;for (int i = 0; i < tot; i ++ )rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));fft(a, 1), fft(b, 1);for (int i = 0; i < tot; i ++ ) a[i] = a[i] * b[i];fft(a, -1);for (int i = 0; i <= n + m; i ++ )printf("%d ", (int)(a[i].x / tot + 0.5));return 0;}
参考：acwing，
【学习笔记】超简单的快速傅里叶变换（FFT）（含全套证明）
