BZOJ 2194 快速傅里葉變換：卷積計算兩序列相關性

問題描述

給定兩個長度 n 序列 a, b，求 c[k] = Σ a[i]·b[i-k]。這是互相關運算，非標準卷積。

轉化為卷積

令 b' 為 b 反序（b'[i] = b[n-1-i]），則：
c[k] = Σ a[i]·b'[n-1-(i-k)] = Σ a[i]·b'[(n-1-k)-i]，即 a 與 b' 的卷積在 n-1-k 處的值。

FFT 實現

1. 將 a, b' 補零到長度 N = 2^{⌈log₂(2n-1)⌉}
2. FFT 變換至頻域，逐點相乘
3. IFFT 變回時域，取實部四捨五入
4. 結果映射回 c[k]

核心代碼

struct Complex {
    double r, i;
    Complex(double _r=0, double _i=0): r(_r), i(_i) {}
    Complex operator+(const Complex& o) const { return {r+o.r, i+o.i}; }
    Complex operator-(const Complex& o) const { return {r-o.r, i-o.i}; }
    Complex operator*(const Complex& o) const { return {r*o.r - i*o.i, r*o.i + i*o.r}; }
};

void fft(vector& a, bool invert) {
    int n = a.size();
    for (int i=1, j=0; i>1;
        for (; j&bit; bit>>=1) j ^= bit;
        j ^= bit;
        if (i multiply(vector a, vector 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 res(n);
    for (int i=0; i

關鍵點

互相關通過反序一個序列轉為卷積
FFT 迭代實現（非遞歸），位反序排列 + 蝶形運算
雙精度浮點足夠處理整數卷積（誤差 < 0.5）
模數題需用 NTT（數論變換），避免浮點誤差


FFT 是多項式乘法、大整數乘法、字符串匹配等問題的核心工具，掌握其迭代實現與卷積應用模板至關重要。