傅里叶变换
复数
定义： x, y 为实数，称形如 (x,y) 的有序数对为复数。
复数 (x, y) 中的第一个实数 x 称为复数 z 的实部，第二个实数 y 称为复数 z 的虚部。
代码实现及运算：
struct Complex{
dou x, y;
Complex(dou xx = 0, dou yy = 0){x = xx, y = yy;}
Complex operator + (Complex &b) const {return Complex(x + b.x, y + b.y);}
Complex operator - (Complex &b) const {return Complex(x - b.x, y - b.y);}
Complex operator * (Complex &b) const {return Complex(x * b.x - y * b.y, x * b.y + b.x * y);}
};
显然乘法不满足交换律。
x + y*i 为复数的代数式，其中i 称为虚数单位，\(i^2\) = -1 。
单位根
FFT就是利用的单位根的性质来实现的
称 \(x^n\)=1 在复数意义下的解是 n 次复根，也称为n个n次单位根或单位副根。
一般叙述的 n 次单位根，是指从 1 开始逆时针方向的第一个解，即上述 \(\omega_n\)，其它解均可以用 \(\omega_n\) 的幂表示。
性质：
1 : \(\omega_n^n\) = 1 //将圆均分为n份，从1出发顺时针旋转n份回到1。
2 : \(\omega_n^k\) = \(\omega_{2n}^{2k}\) //将圆均分后， k/n = 2k/2n。
3 : \(\omega_{2n}^{k+n}\) = - \(\omega_{2n}^k\) //将圆均分为2n份，顺时针旋转n份即旋转了180°。
4：\(\omega_{n}^{k}\) = \(e^{i2\pi\frac{k}{n}}\) = \(i\sin(2\pi\frac{k}{n}) + cos(2\pi\frac{k}{n})\)
傅里叶变换
一般多项式：F(x) = \(a_0\) + \(a_1\)\(x^1\) + \(a_2\)\(x^2\) + \(a_3\)\(x^3\)……
\[F(x) = \sum_{i = 0}^{n-1} \ a_ix^i \]傅立叶正变换：
\[F(\omega_n^s) = \sum_{i = 0}^{n-1} \ a_i*\omega_n^{is} \]傅立叶逆变换：
\[a_j = \frac{1}{n} \sum_{s = 0}^{n-1}\omega^{-js}_n*F(\omega_n^s) \]二维傅里叶正变换：
\[F(\omega_n^t，\omega_n^s) = \sum_{i = 0}^{n-1}\sum_{j = 0}^{n-1} \ a(i, j)*\omega_n^{is}*\omega_n^{it} \]二维傅里叶逆变换：
\[a(i, j) = \frac{1}{n^2} \sum_{s = 0}^{n-1}\sum_{t = 0}^{n-1}\omega^{-it}_n*\omega^{-js}_n*F(\omega_n^t，\omega_n^s) \]FFT快速傅里叶变换
FFT的基本思想就是分治。
对于一个多项式：
\[f(x) = a_0 + a_1x + a_2x^2+a_3x^3+a_4x^4+a_5x^5+a_6x^6+a_7x^7…… \]按照次数的奇偶来分成两组：
\[f(x) = (a_0+a_2x^2+a_4x^4+a_6x^6……) + (a_1x+a_3x^3+a_5x^5+a_7x^7……) \]分别用奇偶次项系数建立新的函数：
\[G(x) = a_0+a_2x+a_4x^2+a_6x^3…… \\ H(x) = a_1+a_3x+a_5x^2+a_7x^3…… \]\[f(x) = G(x^2) +x * H(x^2) \]得到：
\[f(\omega_n^k) = G((\omega_n^k)^2) + \omega_n^k \times H((\omega_n^k)^2) \\= G(\omega_n^{2k}) + \omega_n^k \times H(\omega_n^{2k}) \\ = G(\omega_{\frac{n}{2}}^k) + \omega_n^k \times H(\omega_{\frac{n}{2}}^k) \]和：
\[f(\omega_n^{k}) = G(\omega_n^{2k+n}) + \omega_n^{k+\frac{n}{2}} \times H(\omega_n^{2k+n}) \\ = G(\omega_n^{2k}) - \omega_n^k \times H(\omega_n^{2k}) \\ = G(\omega_{\frac{n}{2}}^k) - \omega_n^k \times H(\omega_{\frac{n}{2}}^k) \]以 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 \} \]对于最后一次二分后下标转二进制会发现：
\[原系数下标：\{000\}\{001\}\{010\}\{011\}\{100\}\{101\}\{110\}\{111\} \]\[三次二分后：\{000\}\{100\}\{010\}\{110\}\{001\}\{101\}\{011\}\{111\} \]二分后结果就是将原下标左右翻转得到。
代码实现：
for(int i = 0; i < lim; i++)
C[i] = (C[i >> 1] >> 1) | (i & 1) << (len - 1);
递推实现P3803：
#include<bits/stdc++.h>
const int N = 1e6 + 10;
using namespace std;
struct complx{
double x, y;
complx (double xx = 0, double yy = 0){x = xx, y = yy;}
}A[N << 2], B[N << 2];
complx operator + (complx a, complx b){return complx(a.x + b.x, a.y + b.y);}
complx operator - (complx a, complx b){return complx(a.x - b.x, a.y - b.y);}
complx operator * (complx a, complx b){return complx(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);}
int H[N << 2], C[N << 2];
int n, m, lim = 1, len;
const double Pi = acos(-1.0);
void FFT(complx *s, int type){
for(int i = 0; i < lim; i++)
if(i < C[i]) swap(s[i], s[C[i]]);
for(int mid = 1; mid < lim; mid <<= 1){
complx Wn (cos(Pi / mid), type * sin(Pi / mid));
for(int R = mid << 1, j = 0; j < lim; j += R){
complx w(1, 0);
for(int k = 0; k < mid; k++, w = w * Wn){
complx x = s[j + k], y = w * s[j + k + mid];
s[j + k] = x + y;
s[j + k + 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(lim <= n + m) lim <<= 1, len++;
for(int i = 0; i < lim; i++)
C[i] = (C[i >> 1] >> 1) | (i & 1) << (len - 1);
FFT(A, 1), FFT(B, 1);
for(int i = 0; i <= lim; i++) A[i] = A[i] * B[i];
FFT(A, -1);
for(int i = 0; i <= n + m; i++) printf("%d ",(int)(A[i].x / lim + 0.5));
return 0;
}