Giới thiệu chung
Vấn đề cốt lõi của tích chập là tìm một dãy số $h$ từ hai dãy $f$ và $g$, sao cho thỏa mãn công thức:
Tại đây, ký hiệu $\oplus$ đại diện cho phép toán cụ thể dùng để phân biệt các dạng tích chập khác nhau. Thông thường, việc tính toán trực tiếp sẽ có độ phức tạp là $O(n^2)$. Mục tiêu của các kỹ thuật dưới đây là tối ưu hóa quá trình này xuống mức thấp hơn.
I. Tích chập Max
Đây là dạng đơn giản nhất, xác định bởi:
Xét điều kiện $i \le x$ để đóng góp vào kết quả tại $x$. Ta có thể áp dụng nguyên lý bù trừ thông qua tổng tiền tố. Nếu định nghĩa $F'(x)$ là tổng tiền tố của $f$ đến $x$, thì tích của các hàm đã chuyển đổi sẽ tương ứng với tổng tiền tố của kết quả cuối cùng:
Quá trình khôi phục giá trị gốc từ tổng tiền tố cũng rất trực quan. Toàn bộ quy trình chỉ yêu cầu độ phức tạp $O(n)$.
Ứng dụng thực tế: Bài toán P7293 liên quan đến việc đếm đường đi trong đồ thị vô hướng trên nhiều thành phần. Vì đồ thị vô hướng cho phép di chuyển qua lại trên cạnh, tính khả thi chỉ phụ thuộc vào tính chẵn lẻ của độ dài đường đi. Bằng cách chạy BFS tìm khoảng cách ngắn nhất lẻ và chẵn cho mỗi đỉnh, bài toán quy về việc tổ hợp các trạng thái bằng phép nhân ma trận hoặc tích chập Max.
II. Tích chập Bitwise (Fast Walsh-Hadamard Transform)
Dành cho các phép toán logic như XOR, AND, OR trên tập hợp nhị phân. Kỹ thuật FWT cho phép biến đổi mảng sang miền khác để thực hiện phép nhân từng phần tử, sau đó chuyển ngược lại.
III. Tích chập Đa thức (FFT và NTT)
Loại phổ biến nhất, ứng dụng cho phép nhân đa thức thông thường:
Một đa thức bậc $n$ được xác định duy nhất bởi $n+1$ cặp điểm giá trị. Nếu chuyển đa thức sang biểu diễn điểm giá trị, phép nhân đa thức trở thành phép nhân từng điểm $(h(x_k) = f(x_k) \cdot g(x_k))$. Vấn đề nằm ở việc chuyển đổi giữa biểu diễn hệ số và điểm giá trị.
1. Căn đơn vị và DFT
Sử dụng căn đơn vị phức $\omega_n = e^{\frac{2\pi i}{n}}$ làm điểm đánh giá. Đa thức $A(x)$ được chia tách theo hệ số chẵn và lẻ:
Khi thay $x = \omega_n^k$, ta thấy $\omega_n^{2k} = \omega_{n/2}^k$. Tính chất này cho phép chia đôi bài toán đệ quy (chia trị và trị).
2. Triển khai đệ quy
Dưới đây là phiên bản sử dụng cấu trúc dữ liệu tùy chỉnh cho số phức để giảm lệ thuộc thư viện:
#include <cmath>
#include <cstdio>
using namespace std;
const int MAX_SIZE = 1<<21;
const double PI_VAL = acos(-1.0);
struct ComplexData {
double r, i; // Phần thực và ảo
ComplexData(double _r=0, double _i=0): r(_r), i(_i){}
};
ComplexData operator+(const ComplexData& a, const ComplexData& b) {
return ComplexData(a.r + b.r, a.i + b.i);
}
ComplexData operator-(const ComplexData& a, const ComplexData& b) {
return ComplexData(a.r - b.r, a.i - b.i);
}
ComplexData operator*(const ComplexData& a, const ComplexData& b) {
return ComplexData(a.r*b.r - a.i*b.i, a.r*b.i + a.i*b.r);
}
ComplexData poly_a[MAX_SIZE], poly_b[MAX_SIZE];
int limit_size = 1;
void transform_recursive(ComplexData* data, int size, double direction) {
if (size == 1) return;
int half = size >> 1;
ComplexData temp_evens[MAX_SIZE], temp_odds[MAX_SIZE];
// Tách chẵn và lẻ
for(int k = 0; k < size; ++k) {
if (k % 2 == 0) temp_evens[k/2] = data[k];
else temp_odds[k/2] = data[k];
}
transform_recursive(temp_evens, half, direction);
transform_recursive(temp_odds, half, direction);
// Kết hợp (Butterfly operation)
ComplexData w_base(cos(2*PI_VAL/size), direction*sin(2*PI_VAL/size));
ComplexData current_w(1, 0);
for(int k = 0; k < half; ++k) {
ComplexData even_val = temp_evens[k];
ComplexData odd_val = temp_odds[k] * current_w;
data[k] = even_val + odd_val;
data[k + half] = even_val - odd_val;
current_w = current_w * w_base;
}
}
3. Triển khai lặp (Không đệ quy)
Để tránh overhead của hàm đệ quy, ta dùng phương pháp hoán vị bit đảo (bit-reversal permutation) trước khi bắt đầu vòng lặp hợp nhất.
void perform_fft_iterative(ComplexData* source, int total_len, bool inverse) {
// Hoán vị bit đảo
for(int i = 0; i < total_len; ++i) {
int rev_idx = reverse_bits(i, log2(total_len));
if (i < rev_idx) swap(source[i], source[rev_idx]);
}
for(int sub_len = 1; sub_len < total_len; sub_len <<= 1) {
ComplexData step_angle(cos(PI_VAL/sub_len), inverse ? -sin(PI_VAL/sub_len) : sin(PI_VAL/sub_len));
for(int start_pos = 0; start_pos < total_len; start_pos += 2*sub_len) {
ComplexData angle_accumulator(1, 0);
for(int k = 0; k < sub_len; ++k) {
ComplexData u = source[start_pos + k];
ComplexData v = source[start_pos + sub_len + k] * angle_accumulator;
source[start_pos + k] = u + v;
source[start_pos + sub_len + k] = u - v;
angle_accumulator = angle_accumulator * step_angle;
}
}
}
if(inverse) {
for(int i = 0; i < total_len; ++i) source[i].r /= total_len;
}
}
4. Số học modulo (NTT)
Để tránh lỗi làm tròn của số phức, ta sử dụng NTT với trường hữu hạn. Cần chọn modulus $P$ dạng $c \cdot 2^k + 1$ (ví dụ 998244353) và căn nguyên thủy $g$. Khi đó, căn đơn vị được thay thế bằng $g^{\frac{P-1}{N}} \pmod P$.
IV. Tích chập Dirichlet
Áp dụng cho các hàm số học với phép toán là ước số:
Cách thực hiện trực tiếp có độ phức tạp $O(n \log n)$ dựa trên cấp số điều hòa. Tuy nhiên, nếu hàm là hàm nhân (multiplicative function), ta có thể tối ưu hơn nhiều.
- Hàm đơn giản: Sử dụng sàng Eratosthenes để tính tổng tiền tố theo từng thừa số nguyên tố.
- Hàm hoàn toàn nhân: Tính độc lập trên từng lũy thừa của số nguyên tố.
Code ví dụ cho việc xử lý hàm Mobius và tổng ước số:
void compute_dirichlet_prefix(int max_n, vector<long long>& values, const vector<int>& primes) {
for(int p : primes) {
// Duyệt bội của số nguyên tố từ lớn đến nhỏ
for(int mult = max_n / p; mult >= 1; --mult) {
if(mult * p > max_n) continue;
// Áp dụng phép biến đổi dựa trên tính chất hàm
long long factor = (p == mu_val[mult]) ? -1 : 1;
values[mult * p] = (values[mult * p] - values[mult] + MOD) % MOD;
}
}
}
Nếu cần tính tích chập của hai hàm nhân, kết quả cũng là hàm nhân. Do đó, chỉ cần tính giá trị tại $p^k$ rồi dùng sàng Euler để mở rộng ra toàn bộ $n$ trong thời gian tuyến tính $O(n)$.
V. Mở rộng nâng cao
1. Lũy thừa nhanh của tích chập
Nếu muốn tính $A^k$ (tích chập tự thân $k$ lần), thay vì nhân $k$ lần, ta có thể đưa sang miền điểm giá trị (qua DFT/FFT), lũy thừa từng điểm giá trị lên $k$, sau đó quay lại. Lưu ý độ dài mảng phải tăng lên đủ để chứa bậc cao nhất.
2. Tích chập nhiều chiều
Khi làm việc với không gian nhiều chiều (ví dụ lưới $N \times M$), các chiều độc lập nhau nên có thể thực hiện tích chập tuần tự trên từng chiều. Ví dụ với ma trận 2D, thực hiện biến đổi trên tất cả các hàng, sau đó thực hiện trên tất cả các cột.
Bài toán ví dụ (AtCoder Ex Problems): Các bài toán như ABC265Ex thường mô hình hóa trò chơi Nim trên lưới hoặc các cấu trúc rời rạc phức tạp. Thay vì mô phỏng trực tiếp, người giải cần nhận diện ma trận kề hoặc vector trạng thái và sử dụng lũy thừa ma trận/tích chập để tính số bước đi hoặc số cách thắng.