快速傅里叶变换（FFT）提高组

💡 核心思想

FFT 是一种在 O(n log n) 时间内计算多项式乘法（卷积）的算法。它利用复数单位根的性质，通过分治策略将系数表示的多项式转换为点值表示，逐点相乘后再逆变换回系数表示。NTT（数论变换）是 FFT 在模意义下的版本，用原根代替复数单位根，避免了浮点数精度问题。

🎯 直觉理解

想象你在计算两个多项式的乘积。普通做法是逐项相乘再合并同类项，复杂度 O(n²)。FFT 的做法更巧妙：它把多项式看成一个波形，通过"频谱分析"把波形分解成不同频率的正弦波（这就是"傅里叶变换"）。两个波形的乘积等于它们频谱的逐点乘积。然后再把频谱合成回波形。整个过程就像把问题从"时域"转换到"频域"再转换回来。

📝 算法流程

1. 确定变换长度 N = 大于 n+m 的最小 2 的幂次
2. 初始化复数数组，补零到长度 N
3. 迭代 FFT：
4. 按二进制位反转重排数组（蝴蝶操作）
5. 逐层合并：len = 2, 4, 8, ... , N
6. 每层用单位根合并奇偶子序列
7. 点值相乘：C[k] = A[k] · B[k]
8. 逆 FFT：用共轭单位根，结果除以 N

$$\omega_n = e^{2\pi i / n}\text{（n 次单位根）}$$

$$\text{FFT: } A_k = \sum_{j=0}^{n-1} a_j \omega_n^{jk},\quad \text{逆 FFT: } a_j = \frac{1}{n}\sum_{k=0}^{n-1} A_k \omega_n^{-jk}$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;
using cd = complex;
const double PI = acos(-1);

void fft(vector& a, bool invert) {
    int n = a.size();
    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]);
    }
    for (int len = 2; len <= n; len <<= 1) {
        double ang = 2 * PI / len * (invert ? -1 : 1);
        cd wlen(cos(ang), sin(ang));
        for (int i = 0; i < n; i += len) {
            cd w(1);
            for (int j = 0; j < len / 2; j++) {
                cd u = a[i+j], v = a[i+j+len/2] * w;
                a[i+j] = u + v;
                a[i+j+len/2] = u - v;
                w *= wlen;
            }
        }
    }
    if (invert)
        for (cd& x : a) x /= n;
}

vector multiply(vector const& a, vector const& b) {
    vector fa(a.begin(), a.end()), fb(b.begin(), b.end());
    int n = 1;
    while (n < a.size() + b.size()) n <<= 1;
    fa.resize(n); fb.resize(n);
    fft(fa, false); fft(fb, false);
    for (int i = 0; i < n; i++) fa[i] *= fb[i];
    fft(fa, true);
    vector res(n);
    for (int i = 0; i < n; i++) res[i] = round(fa[i].real());
    return res;
}

int main() {
    vector a = {1, 2, 3}; // 1 + 2x + 3x²
    vector b = {4, 5};    // 4 + 5x
    auto c = multiply(a, b);
    for (ll x : c) cout << x << " "; // 4 13 22 15
    cout << endl;
    return 0;
}

⚠️ 常见坑点

📚 相关题目