一、FFT 要解决的问题：多项式乘法喵~

假设有两个多项式喵~：

\(A(x) = a_0 + a_1x + a_2x^2 + \dots + a_{n-1}x^{n-1}\)

\(B(x) = b_0 + b_1x + b_2x^2 + \dots + b_{n-1}x^{n-1}\)

我们需要求出它们的积 \(C(x) = A(x) \times B(x)\) 喵~。

• 暴力做法：双重循环将每一项两两相乘再合并，复杂度是 \(O(n^2)\) 喵~。

• FFT 的目标：在 \(O(n \log n)\) 时间内算出 \(C(x)\) 喵~。

---

二、核心思想：从“系数表示”到“点值表示”喵~

多项式有两种表示方法喵~：

• 系数表示法（我们平时用的）喵~：
  \(A(x) = [a_0, a_1, \dots, a_{n-1}]\) 喵~。
  乘法代价：\(O(n^2)\) 喵~。

• 点值表示法喵~：
  平面上 \(n\) 个不同的点可以唯一确定一个 \(n-1\) 次多项式喵~。
  选取 \(n\) 个点 \(x_0, x_1, \dots, x_{n-1}\)，代入得到对应的纵坐标 \((x_k, y_k)\) 喵~。
  乘法代价：极快喵~！对于同一个横坐标 \(x_k\)，\(C(x_k) = A(x_k) \times B(x_k)\) 喵~。只需 \(O(n)\) 次乘法即可得到 \(C(x)\) 的点值喵~。

表示法转换	流程	算法	时间复杂度
系数 \(\to\) 点值（求值）喵~	DFT（用 FFT 加速）喵~	\(O(n \log n)\) 喵~
点值 \(\times\) 点值（相乘）喵~	对应点相乘喵~	\(O(n)\) 喵~
点值 \(\to\) 系数（插值）喵~	IDFT（用 IFFT 加速）喵~	\(O(n \log n)\) 喵~

FFT 的本质：就是利用分治法，在 \(O(n \log n)\) 时间内完成系数和点值之间的互相转换喵~。

---

三、关键突破口：单位复数根喵~

如果我们随便选 \(n\) 个点代入，求值依然需要 \(O(n^2)\) 喵~。FFT 的巧妙之处在于：代入一组特殊的复数——单位根喵~。

满足 \(z^n = 1\) 的复数 \(z\) 称为 \(n\) 次单位根喵~。

在复平面上，这 \(n\) 个解均匀分布在以原点为圆心的单位圆上，把圆周 \(n\) 等分喵~。

记主单位根为 \(\omega_n = e^{i \frac{2\pi}{n}} = \cos\left(\frac{2\pi}{n}\right) + i\sin\left(\frac{2\pi}{n}\right)\) 喵~。

这 \(n\) 个点分别为：\(\omega_n^0, \omega_n^1, \omega_n^2, \dots, \omega_n^{n-1}\) 喵~。

单位根的 3 个神仙性质喵~：

• 折半引理（消去公因数）：\(\omega_{2n}^{2k} = \omega_n^k\) 喵~
• 对称引理（相反数）：\(\omega_n^{k + n/2} = -\omega_n^k\) 喵~
• 周期性：\(\omega_n^n = \omega_n^0 = 1\) 喵~

---

四、分治加速（Cooley-Tukey 算法）喵~

假设多项式项数 \(n\) 是 \(2\) 的幂（若不是，高位补 0 补齐）喵~。

我们将 \(A(x)\) 按系数下标的奇偶性拆成两部分喵~：

\[A(x) = (a_0 + a_2x^2 + \dots) + x(a_1 + a_3x^2 + \dots)\]

设喵~：

\(A_1(x) = a_0 + a_2x + a_4x^2 + \dots\) （偶数项）喵~

\(A_2(x) = a_1 + a_3x + a_5x^2 + \dots\) （奇数项）喵~

则有喵~：

\[A(x) = A_1(x^2) + x A_2(x^2)\]

现在把单位根 \(\omega_n^k\)（\(k < \frac{n}{2}\)）代入喵~：

前半部分（\(k\)）喵~：

\[A(\omega_n^k) = A_1(\omega_n^{2k}) + \omega_n^k A_2(\omega_n^{2k}) = A_1(\omega_{n/2}^k) + \omega_n^k A_2(\omega_{n/2}^k)\]

后半部分（\(k + \frac{n}{2}\)，利用对称引理）喵~：

\[A(\omega_n^{k + n/2}) = A_1(\omega_{n/2}^k) - \omega_n^k A_2(\omega_{n/2}^k)\]

发现奇迹了吗喵~？

只要算出了子问题 \(A_1(\omega_{n/2}^k)\) 和 \(A_2(\omega_{n/2}^k)\)，我们就可以同时得到前半部分 \(A(\omega_n^k)\) 和后半部分 \(A(\omega_n^{k+n/2})\) 喵~！

这就是经典的分治：规模为 \(n\) 的问题拆成两个规模为 \(n/2\) 的子问题，递推式为 \(T(n) = 2T(n/2) + O(n)\)，复杂度为 \(O(n \log n)\) 喵~。

---

五、如何逆变换（IFFT / IDFT）？喵~

把点值重新变回系数的过程叫 IDFT 喵~。

数学上可以严格证明：IDFT 和 DFT 的公式几乎一模一样，只需把单位根 \(\omega_n^k\) 换成它的共轭复数 \(\omega_n^{-k}\)，最后结果除以 \(n\) 即可喵~。

因此，正变换和逆变换可以用同一套代码搞定喵~！

---

六、信竞实战必知：蝴蝶变换与迭代实现喵~

递归写法的 FFT 常数较大，容易爆栈或 TLE 喵~。在实际竞赛中，通常采用非递归（迭代）写法喵~。

观察分治过程中下标的二进制变化，可以发现：最终底层的元素顺序，刚好是原下标二进制反转（Bit-Reversal）后的顺序喵~。

例：\(n=8\) 时，下标 \(1\)（二进制 001）反转后是 100（即下标 \(4\)）喵~。

预处理二进制反转数组（雷德算法），即可自底向上循环迭代计算（即蝴蝶操作）喵~。

简易 C++ 代码框架参考喵~

#include <iostream>
#include <complex>
#include <cmath>
#include <vector>
using namespace std;

const double PI = acos(-1.0);
typedef complex<double> cd;

// type = 1 为 FFT, type = -1 为 IFFT
void fft(vector<cd>& a, int n, int type) {
    // 1. 位逆序置换 (Bit-Reversal Permutation)
    for (int i = 1, j = 0; i < n; ++i) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1) j ^= bit;
        j ^= bit;
        if (i < j) swap(a[i], a[j]);
    }
    
    // 2. 自底向上蝴蝶变换
    for (int len = 2; len <= n; len <<= 1) {
        double angle = 2 * PI / len * type;
        cd wlen(cos(angle), sin(angle));
        for (int i = 0; i < n; i += len) {
            cd w(1);
            for (int j = 0; j < len / 2; ++j) {
                cd u = a[i + j];
                cd v = w * a[i + j + len / 2];
                a[i + j] = u + v;
                a[i + j + len / 2] = u - v;
                w *= wlen;
            }
        }
    }
    
    if (type == -1) {
        for (int i = 0; i < n; ++i) a[i] /= n;
    }
}

---

学习建议与后续路线喵~

先过模板题：去洛谷刷一下 P3803 【模板】多项式乘法 (FFT)，亲手写一遍蝴蝶变换加深理解喵~。

进阶学习喵~：

• NTT（快速数论变换）：用模意义下的原根替代复数单位根，避免浮点数精度误差（OI 中更常用喵~！）。
• 多项式全家桶：求逆、除法、对数/指数函数（多项式 \(\ln\) / \(\exp\)）等喵~。