Wiki › Thuật toán › Toán học › FFT (Fast Fourier Transform)

FFT (Fast Fourier Transform)

huunguyen Updated Tháng sáu 1, 2026

FFT (Fast Fourier Transform — Biến đổi Fourier nhanh) là thuật toán nhân hai đa thức bậc $N$ trong $O (N \log N)$ thay vì $O (N^{2})$ của cách nhân từng cặp hệ số. Trong lập trình thi đấu, FFT (và biến thể số học NTT) được dùng chủ yếu để nhân đa thức và tính tích chập (convolution) — chẳng hạn "với mỗi $k$ , đếm số cặp $(i, j)$ sao cho $i + j = k$ ". Bất kỳ bài nào có dạng

$c_{k} = \sum_{i + j = k} a_{i} \cdot b_{j}$

đều là tích chập và có thể tăng tốc bằng FFT/NTT.

Ý tưởng / Trực giác

Tại sao nhân đa thức lại tốn $O (N^{2})$ ? Vì biểu diễn theo hệ số $A (x) = a_{0} + a_{1} x + \dots + a_{n - 1} x^{n - 1}$ buộc ta nhân chéo mọi cặp hệ số.

Mấu chốt: một đa thức bậc $< n$ được xác định duy nhất bởi giá trị của nó tại $n$ điểm phân biệt (giống như 2 điểm xác định 1 đường thẳng, 3 điểm xác định 1 parabol). Nếu ta biết giá trị của $A$ và $B$ tại cùng một bộ điểm $x_{0}, x_{1}, \dots$ , thì tích $C = A \cdot B$ tại mỗi điểm chỉ là phép nhân hai số:

$C (x_{t}) = A (x_{t}) \cdot B (x_{t})$

Tức là ở "miền giá trị", nhân đa thức chỉ tốn $O (N)$ . Vậy chiến lược 3 bước:

Evaluate (chuyển hệ số → giá trị): tính $A$ , $B$ tại $2 N$ điểm.
Pointwise multiply: nhân từng cặp giá trị — $O (N)$ .
Interpolate (chuyển giá trị → hệ số): khôi phục đa thức tích từ các giá trị.

Nếu chọn điểm tùy tiện thì bước 1 và 3 vẫn tốn $O (N^{2})$ . Phép màu của FFT là chọn điểm thông minh: các căn đơn vị (roots of unity) $ω_{n}^{k} = e^{2 π i k / n}$ . Chúng có tính chất $ω_{n}^{k + n / 2} = - ω_{n}^{k}$ , nên khi chia đa thức thành phần chẵn và lẻ:

$A (x) = A_{chẵn} (x^{2}) + x \cdot A_{lẻ} (x^{2})$

giá trị tại $ω_{n}^{k}$ và tại $ω_{n}^{k + n / 2}$ dùng chung $A_{chẵn} (x^{2})$ , $A_{lẻ} (x^{2})$ . Đây chính là chia để trị: mỗi tầng gộp 2 nửa trong $O (n)$ , có $\log n$ tầng, ra $O (N \log N)$ . Bước interpolate (IFFT) giống hệt FFT nhưng dùng $ω_{n}^{- k}$ rồi chia cho $n$ .

NTT (Number Theoretic Transform) thay căn đơn vị phức bằng căn nguyên thủy trong trường $ℤ / p ℤ$ . Nó cần $p$ là số nguyên tố dạng $c \cdot 2^{k} + 1$ để tồn tại "căn bậc $2^{k}$ của đơn vị". Lợi ích: chỉ dùng số nguyên, không có sai số dấu phẩy động, và trả kết quả sẵn theo modulo — nên trong thi đấu thường ưu tiên NTT.

Ví dụ chạy tay: nhân hai đa thức

Nhân $A (x) = 1 + 2 x + 3 x^{2}$ với $B (x) = 4 + 5 x$ . Kết quả đúng (nhân tay):

$A \cdot B = 4 + 13 x + 22 x^{2} + 15 x^{3}$

Hình dung quá trình theo 3 bước (ở đây minh họa bằng "điểm" tổng quát; FFT thực tế chọn điểm là căn đơn vị, nhưng nguyên lý y hệt). Tích có bậc $3$ nên cần ít nhất $4$ điểm; ta lấy luôn $n = 4$ :

Hệ số:   A = [1, 2, 3, 0]      B = [4, 5, 0, 0]
              ^padding cho đủ n=4 (lũy thừa của 2)

Bước 1 — EVALUATE tại 4 điểm x0..x3 (FFT):
          A(x0) A(x1) A(x2) A(x3)
   A  →  [ vA0   vA1   vA2   vA3 ]
   B  →  [ vB0   vB1   vB2   vB3 ]

Bước 2 — POINTWISE MULTIPLY (nhân từng cột):
   C  →  [vA0*vB0, vA1*vB1, vA2*vB2, vA3*vB3]
            ^ cột đang nhân: chỉ O(1) mỗi cột

Bước 3 — INTERPOLATE (IFFT) → quay lại hệ số:
   C  →  [4, 13, 22, 15]
          c0  c1  c2  c3

Kiểm chứng từng hệ số bằng định nghĩa tích chập $c_{k} = \sum_{i + j = k} a_{i} b_{j}$ :

$k$	các cặp $(i, j)$ với $i + j = k$	$c_{k}$
0	$(0, 0)$	$1 \cdot 4 = 4$
1	$(0, 1), (1, 0)$	$1 \cdot 5 + 2 \cdot 4 = 13$
2	$(1, 1), (2, 0)$	$2 \cdot 5 + 3 \cdot 4 = 22$
3	$(2, 1)$	$3 \cdot 5 = 15$

Khớp với $[4, 13, 22, 15]$ .

Cài đặt

Dưới đây là NTT in-place (Cooley–Tukey, kiểu lặp) với mod thông dụng $998244353 = 119 \cdot 2^{23} + 1$ , căn nguyên thủy $g = 3$ (hỗ trợ độ dài tới $2^{23}$ ).

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

const long long MOD = 998244353;
const long long g   = 3;            // căn nguyên thủy của MOD

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: vector hệ số (độ dài là lũy thừa của 2).
// invert = false: thuận (hệ số -> giá trị); true: nghịch (giá trị -> hệ số).
void ntt(vector<long long>& a, bool invert) {
    int n = a.size();

    // Bước 1: hoán vị bit-reversal để biến đệ quy thành lặp tại chỗ.
    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]);
    }

    // Bước 2: gộp dần các đoạn độ dài 2, 4, 8, ... (butterfly)
    for (int len = 2; len <= n; len <<= 1) {
        // w = căn bậc len của đơn vị (hoặc nghịch đảo nếu invert)
        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;                 // wn = w^j chạy trong đoạn
            for (int j = 0; j < len / 2; j++) {
                long long u = a[i + j];
                long long v = a[i + j + len/2] * wn % MOD;
                a[i + j]           = (u + v) % MOD;          // butterfly trên
                a[i + j + len/2]   = (u - v + MOD) % MOD;    // butterfly dưới (+MOD tránh âm)
                wn = wn * w % MOD;
            }
        }
    }

    // Bước 3: nếu nghịch, chia tất cả cho n (nhân nghịch đảo modulo)
    if (invert) {
        long long n_inv = power(n, MOD - 2, MOD);  // n^{-1} theo Fermat
        for (auto& x : a) x = x * n_inv % MOD;
    }
}

// Nhân hai đa thức a, b (kết quả lấy theo modulo MOD)
vector<long long> multiply(vector<long long> a, vector<long long> b) {
    int result_size = (int)a.size() + (int)b.size() - 1;
    int n = 1;
    while (n < result_size) n <<= 1;   // làm tròn lên lũy thừa của 2
    a.resize(n); b.resize(n);

    ntt(a, false); ntt(b, false);                  // sang miền giá trị
    for (int i = 0; i < n; i++) a[i] = a[i] * b[i] % MOD;  // nhân điểm-điểm
    ntt(a, true);                                  // quay lại hệ số

    a.resize(result_size);             // bỏ phần padding thừa
    return a;
}

Dùng cho ví dụ trên:

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

Tích chập đếm cặp (ví dụ đếm số cặp $(i, j)$ với $i + j = k$ ): đặt $f [v]$ = số lần giá trị $v$ xuất hiện ở mảng thứ nhất, $g [v]$ tương tự cho mảng thứ hai, rồi lấy multiply(f, g); hệ số $k$ chính là số cặp có tổng $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

Độ phức tạp

Thao tác	Thời gian	Vì sao
Một lần NTT/FFT	$O (N \log N)$	$\log N$ tầng butterfly, mỗi tầng duyệt toàn bộ $N$ phần tử một lần
Nhân hai đa thức bậc $N$	$O (N \log N)$	3 lần biến đổi $O (N \log N)$ + một vòng nhân điểm-điểm $O (N)$
Bộ nhớ	$O (N)$	giữ vài mảng độ dài $n$ (lũy thừa của 2 gần nhất $\geq$ kích thước tích)

Lưu ý $N$ ở đây là kích thước sau khi làm tròn lên lũy thừa của 2: nếu tích có $2 \times 10^{5}$ hệ số thì $n$ nhảy lên $2^{18} = 262144$ . So với cách ngây thơ $O (N^{2}) \approx 4 \times 10^{10}$ phép tính (quá chậm), FFT/NTT chỉ tốn cỡ $N \log N \approx 5 \times 10^{6}$ — đó là lý do nó bắt buộc khi $N$ tới hàng trăm nghìn.

⚠️ Lỗi thường gặp

Tràn số khi nhân: trong NTT ta liên tục tính a * b % MOD. Với $MOD \approx 10^{9}$ , tích a * b xấp xỉ $10^{18}$ — vượt int rất xa. Phải dùng long long cho mọi biến tham gia nhân (kể cả biến trung gian u, v, wn). Quên long long → kết quả sai âm thầm, không báo lỗi.
Kết quả modulo bị âm: ở bước butterfly dưới (u - v) có thể âm. Bắt buộc (u - v + MOD) % MOD. Quên + MOD thì có hệ số ra số âm và mọi phép sau hỏng theo.
Không làm tròn lên lũy thừa của 2: NTT/FFT chỉ chạy đúng khi độ dài là lũy thừa của 2. Nếu để $n$ bằng đúng a.size()+b.size()-1 (thường không phải lũy thừa của 2) thì hoán vị bit-reversal và các tầng gộp đều sai. Luôn while (n < result_size) n <<= 1.
Cấp phát $n$ quá nhỏ: tích của hai đa thức bậc $d_{1}, d_{2}$ có bậc $d_{1} + d_{2}$ , tức $d_{1} + d_{2} + 1$ hệ số. Nếu chỉ resize bằng $max$ kích thước hai đầu vào, các hệ số bậc cao bị "cuộn vòng" (do FFT làm việc theo modulo $x^{n} - 1$ ) và cộng nhầm vào hệ số bậc thấp. Phải lấy $n \geq$ tổng độ dài.
Nghịch đảo modulo khi MOD không nguyên tố: cài n_inv = power(n, MOD-2, MOD) dựa trên định lý Fermat, chỉ đúng khi MOD là số nguyên tố. Với NTT mod $998244353$ thì ổn; nhưng nếu bài yêu cầu trả kết quả theo $10^{9} + 7$ (không phải dạng $c \cdot 2^{k} + 1$ , không có căn nguyên thủy bậc lớn) thì không thể dùng NTT trực tiếp — phải dùng FFT số phức rồi quy về $10^{9} + 7$ , hoặc NTT nhiều mod + CRT.
Sai số FFT số phức: nếu dùng FFT với complex<double> thay vì NTT, hệ số tích phải làm tròn llround. Khi hệ số lớn (vd nhân hai mảng giá trị tới $10^{9}$ ) sai số double có thể lệch $\geq 0.5$ và làm tròn sai. Khi cần độ chính xác tuyệt đối theo modulo, hãy chọn NTT.

Biến thể / Mở rộng

FFT số phức: dùng khi không cần modulo (vd nhân số nguyên lớn, đếm thực). Thay căn nguyên thủy bằng exp(2*PI*i/n), cuối cùng llround phần thực.
NTT nhiều modulo + CRT: khi bài bắt modulo $10^{9} + 7$ , chạy NTT với 2–3 mod NTT-friendly khác nhau rồi ghép bằng định lý số dư Trung Hoa để khôi phục kết quả đúng.
Liên hệ tích chập khác: XOR-convolution / AND / OR convolution dùng biến đổi Walsh–Hadamard (SOS DP), không phải FFT, nhưng cùng tư tưởng "biến đổi → nhân điểm-điểm → biến đổi ngược".

Bài tập luyện

Convoluted Intervals (convintv) — (Advanced) Đếm với mỗi $k$ số cặp đoạn $(i, j)$ có $a_{i} + a_{j} \leq k \leq b_{i} + b_{j}$ : chính là tích chập phân bố đầu mút, bài nhập môn kinh điển để nhìn ra cấu trúc convolution.
Xử Lý Tín Hiệu (sigproc) — (Expert) Trượt mặt nạ $b$ qua tín hiệu $a$ rồi lấy tổng tích — đúng định nghĩa tích chập; với $n, m$ tới $2 \times 10^{5}$ buộc phải dùng FFT/NTT thay vì nhân trực tiếp $O (n m)$ .