BZOJ 2194 快速傅立葉之二：陣列反序轉化卷積

題目大意

計算 C[k] = Σ_{i=k}^{n-1} a[i] × b[i-k]，其中 n ≤ 10⁵，a,b 元素為 ≤100 的非負整數。

核心洞察：反序即卷積

令 b'[i] = b[n-1-i]（反序），則：

C[k] = Σ_i a[i] × b'[n-1-(i-k)] = Σ_i a[i] × b'[(n-1-k)-i]

這正是 a 與 b' 的卷積在索引 (n-1-k) 處的值！

FFT 實作要點

• 長度取 2 的冪 ≥ 2n
• 輸入為整數，輸出四捨五入取整
• 精度：雙精度 FFT 對 ≤100 整數卷積完全足夠

完整程式碼 (C++)

#include <bits/stdc++.h>
using namespace std;

const double PI = acos(-1.0);

struct Complex {
    double x, y;
    Complex(double _x=0, double _y=0): x(_x), y(_y) {}
    Complex operator+(const Complex& o) const { return Complex(x+o.x, y+o.y); }
    Complex operator-(const Complex& o) const { return Complex(x-o.x, y-o.y); }
    Complex operator*(const Complex& o) const { return Complex(x*o.x - y*o.y, x*o.y + y*o.x); }
};

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n; cin >> n;
    vector<double> a(n), b(n);
    for (int i=0; i<n; ++i) {
        cin >> a[i] >> b[n-1-i];  // 讀入時直接反序存 b
    }
    
    int N = 1;
    while (N < 2*n) N <<= 1;
    a.resize(N); b.resize(N);
    
    vector<Complex> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    fft(fa, false); fft(fb, false);
    for (int i=0; i<N; ++i) fa[i] = fa[i] * fb[i];
    fft(fa, true);
    
    for (int k=0; k<n; ++k) {
        // 卷積結果索引 n-1+k 對應 C[k]
        ll ans = (ll)(fa[n-1+k].x + 0.5);
        cout << ans << '\n';
    }
    return 0;
}

範例驗證

輸入：
5
3 1
2 4
1 1
2 4
1 4

輸出：
24
12
10
6
1

複雜度與延伸

• 時間：O(n log n)，n=10⁵ 約 0.1 秒內完成
• 同類題型：BZOJ 2179 (大整數乘法)、BZOJ 3527 (場強計算)
• 關鍵模式：C[k] = Σ a[i]b[i-k] → 反序 b → 卷積