FFT (Fast Fourier Transform)

Wiki › Thuật toán › Toán học

huunguyen · Last updated 8, Tháng 4, 2026, 15:30

FFT (Fast Fourier Transform) là thuật toán nhân hai đa thức bậc $N$ trong $O (N \log N)$ thay vì $O (N^{2})$ thông thường. Trong lập trình thi đấu, FFT được dùng chủ yếu để nhân đa thức và tính tích chập (convolution).

Ý tưởng

Nhân hai đa thức $A$ và $B$ theo 3 bước:

Evaluate: Biểu diễn $A$ và $B$ qua giá trị tại $2 N$ điểm (dùng FFT — $O (N \log N)$ ).
Pointwise multiply: Nhân từng cặp giá trị — $O (N)$ .
Interpolate: Khôi phục đa thức tích từ các giá trị (dùng IFFT — $O (N \log N)$ ).

FFT chọn các điểm là căn đơn vị $ω_{n}^{k} = e^{2 π i k / n}$ , cho phép chia để trị hiệu quả.

Cài đặt — NTT (Number Theoretic Transform)

Trong thi đấu, dùng NTT thay FFT để tránh sai số dấu phẩy động. NTT hoạt động trên $ℤ / p ℤ$ với $p$ là số nguyên tố dạng $c \cdot 2^{k} + 1$ (có căn nguyên thủy).

Mod phổ biến: $998244353 = 119 \cdot 2^{23} + 1$ , căn nguyên thủy $g = 3$ .

const int MOD = 998244353;
const int g = 3;   // primitive root

long long power(long long a, long long b, long long mod) {
    long long res = 1; a %= mod;
    for (; b; b >>= 1) { if (b & 1) res = res * a % mod; a = a * a % mod; }
    return res;
}

// NTT in-place: a là vector hệ số, invert=true cho INTT
void ntt(vector<long long>& 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) {
        long long w = invert ? power(g, MOD - 1 - (MOD - 1) / len, MOD)
                             : power(g, (MOD - 1) / len, MOD);
        for (int i = 0; i < n; i += len) {
            long long wn = 1;
            for (int j = 0; j < len / 2; j++) {
                long long u = a[i+j], v = a[i+j+len/2] * wn % MOD;
                a[i+j]         = (u + v) % MOD;
                a[i+j+len/2]   = (u - v + MOD) % MOD;
                wn = wn * w % MOD;
            }
        }
    }

    if (invert) {
        long long n_inv = power(n, MOD - 2, MOD);
        for (auto& x : a) x = x * n_inv % MOD;
    }
}

// Nhân hai đa thức a và b (mod MOD)
vector<long long> multiply(vector<long long> a, vector<long long> b) {
    int result_size = a.size() + b.size() - 1;
    int n = 1;
    while (n < result_size) n <<= 1;
    a.resize(n); b.resize(n);

    ntt(a, false); ntt(b, false);
    for (int i = 0; i < n; i++) a[i] = a[i] * b[i] % MOD;
    ntt(a, true);

    a.resize(result_size);
    return a;
}

Ví dụ: Nhân đa thức

// A(x) = 1 + 2x + 3x^2
// B(x) = 4 + 5x
// A*B = 4 + 13x + 22x^2 + 15x^3

vector<long long> a = {1, 2, 3};
vector<long long> b = {4, 5};
auto c = multiply(a, b);
// c = {4, 13, 22, 15}

Ví dụ: Tính tích chập

Đếm số cặp $(i, j)$ với $i \in A$ , $j \in B$ sao cho $i + j = k$ :

// Tạo đa thức: f[i] = 1 nếu i ∈ A, g[j] = 1 nếu j ∈ B
// Tích f*g: hệ số k là số cặp (i,j) với i+j=k
vector<long long> f(MAXV, 0), gg(MAXV, 0);
for (int x : A) f[x]++;
for (int x : B) gg[x]++;
auto res = multiply(f, gg);
// res[k] = số cặp (i,j) với i+j=k

FFT với số thực (khi mod không phải 998244353)

#include <complex>
using cd = complex<double>;
const double PI = acos(-1);

void fft(vector<cd>& 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 (auto& x : a) x /= n;
}

Lưu ý: FFT số thực có thể bị sai số — dùng llround() để làm tròn kết quả.

Độ phức tạp

	Độ phức tạp
NTT / FFT	$O (N \log N)$
Nhân đa thức bậc $N$	$O (N \log N)$
Tích chập hai mảng kích thước $N$	$O (N \log N)$

Khi nào dùng FFT/NTT?

Nhân đa thức bậc lớn.
Đếm cặp $(i, j)$ thỏa $i + j = k$ (string matching, counting).
Bài toán subset sum với tích chập.
Khi bài toán có cấu trúc convolution ẩn.

Bình luận

Không có bình luận tại thời điểm này.