Hàm sinh (Generating Functions)
Đóng gói một dãy số thành chuỗi lũy thừa để biến các bài đếm thành phép nhân, chia đa thức. Gồm bổ đề nhân, hàm sinh hữu tỷ và truy hồi tuyến tính, hàm sinh mũ, cài đặt nhân cắt cụt và nghịch đảo chuỗi.
Hàm sinh (generating function) là cách "đóng gói" cả một dãy số vào một đối tượng duy nhất: chuỗi lũy thừa hình thức . Ta không thay số vào ; chỉ là "nhãn" đánh dấu vị trí thứ . Sức mạnh của nó nằm ở chỗ các thao tác đếm quen thuộc (chọn độc lập, cộng dồn, dịch chỉ số) trở thành phép toán đại số trên đa thức: nhân, chia, đạo hàm.
Trong competitive programming, hàm sinh thường xuất hiện ở ba dạng: (1) đếm số cách chọn với tổng cố định khi mỗi thành phần có tập giá trị riêng (chia kẹo, đổi tiền, đếm hoán vị theo số nghịch thế); (2) biến bài đếm thành dạng , tức một dãy truy hồi tuyến tính, rồi lấy hệ số ở tới ; (3) với bậc tới hoặc , kết hợp NTT để nhân, nghịch đảo, lấy và của chuỗi trong . Trang này tập trung vào tư duy và các phép toán hoặc cơ bản; phần tăng tốc bằng NTT xem trang FFT.
Ý tưởng / Trực giác
Ký hiệu là hệ số của trong .
Bổ đề nhân (quy tắc nhân của phép đếm). Nếu đếm số cách chọn một đối tượng loại 1 có "trọng lượng" , và đếm tương tự cho loại 2, thì số cách chọn một cặp (mỗi loại một đối tượng, độc lập) có tổng trọng lượng là
Chứng minh: khai triển tích, mỗi cặp góp đúng một số hạng ; gom theo lũy thừa của là xong. Vì tự động "cộng trọng lượng", phép nhân đa thức chính là phép đếm tích Descartes theo tổng. Mọi ứng dụng bên dưới đều xuất phát từ bổ đề này.
Từ điển hàm sinh hay gặp (kiểm chứng bằng cách nhân hai vế với mẫu số):
| Dãy | Hàm sinh | Ý nghĩa đếm |
|---|---|---|
| chọn một số bất kỳ | ||
| số , rồi toàn | chọn một số trong | |
| chọn một số nguyên dương | ||
| chia viên kẹo cho bạn | ||
| (Fibonacci) | lát dải bằng ô dài 1 và 2 |
Các phép biến đổi. Nhân với : dịch dãy sang phải chỗ. Nhân với : lấy tổng tiền tố (). Nhân với : lấy hiệu kề. Nhân với : tổng của hệ số liên tiếp, làm được trong bằng tổng tiền tố thay vì .
Hàm sinh hữu tỷ tương đương dãy truy hồi tuyến tính. Nếu với và , thì từ , so sánh hệ số với :
Ngược lại, mọi dãy truy hồi tuyến tính hệ số hằng đều có hàm sinh hữu tỷ. Vì vậy một bài đếm mà ta viết được thành với nhỏ thì lấy hệ số thứ được bằng nhân ma trận hoặc thuật toán Bostan-Mori. Còn khi cần mọi hệ số tới , ta chia chuỗi trực tiếp: với , hệ số của thỏa với mọi , nên
Hàm sinh mũ (EGF). Khi các đối tượng được gán nhãn (hoán vị, phân hoạch tập hợp, xếp thứ tự thao tác), dùng . Tích hai EGF cho : hệ số nhị thức tự động đếm cách chia nhãn cho hai phần. Ví dụ, số cách xếp thao tác khi người thứ làm thao tác là hệ số đa thức , chính là nhân hệ số của tích các EGF .
Mẹo phần bù và cắt cụt. Đếm "có ít nhất một phần tử bằng " thường quy về đếm phần bù "không phần tử nào bằng ": hàm sinh một phần tử đổi từ thành . Và vì chỉ cần hệ số tới bậc , mọi phép nhân đều làm theo modulo : hệ số bậc cao bị bỏ ngay, chi phí không phụ thuộc vào bậc thật của đa thức.
Ví dụ chạy tay
Bài: chia viên kẹo cho 3 bạn, bạn 1 nhận tối đa 2 viên, bạn 2 tối đa 1 viên, bạn 3 tối đa 3 viên. Có bao nhiêu cách với mỗi ?
Theo bổ đề nhân, đáp án là các hệ số của
Nhân lần lượt từng thừa số. Bước 1: . Bước 2 nhân với bằng tổng trượt cửa sổ độ dài 4 ():
f (sau bước 1): 1 2 2 1 0 0 0
s=0 s=1 s=2 s=3 s=4 s=5 s=6
g_0 = f0 = 1
g_1 = f1+f0 = 3
g_2 = f2+f1+f0 = 5
g_3 = f3+f2+f1+f0 = 6
g_4 = f3+f2+f1 = 5
g_5 = f3+f2 = 3
g_6 = f3 = 1
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|---|
| số cách | 1 | 3 | 5 | 6 | 5 | 3 | 1 |
Kiểm chứng bằng liệt kê : , đúng 6 cách. Tổng các hệ số là : thay đếm mọi cách không quan tâm tổng.
Chia chuỗi: với (nạp vào modulo là ), công thức cho , và 11 hệ số đầu của là : đúng dãy Fibonacci.
Cài đặt
Các hàm dưới đây làm việc theo modulo và cắt mọi kết quả ở bậc .
Nhân đa thức cắt cụt và nhân với
const long long MOD = 998244353;
long long power(long long a, long long b) {
long long res = 1;
a %= MOD;
if (a < 0) a += MOD;
for (; b > 0; b >>= 1) {
if (b & 1) res = res * a % MOD;
a = a * a % MOD;
}
return res;
}
// Nhân hai đa thức, chỉ giữ các hệ số bậc <= K (phép nhân chập cắt cụt)
vector<long long> mul_trunc(const vector<long long>& a, const vector<long long>& b, int K) {
vector<long long> c(K + 1, 0);
for (int i = 0; i < (int)a.size() && i <= K; i++) {
if (a[i] == 0) continue;
for (int j = 0; j < (int)b.size() && i + j <= K; j++)
c[i + j] = (c[i + j] + a[i] * b[j]) % MOD;
}
return c;
}
// Nhân f với (1 + x + ... + x^c), giữ bậc <= K, O(K) bằng tổng tiền tố:
// g[s] = f[s] + f[s-1] + ... + f[s-c]
vector<long long> mul_bounded(const vector<long long>& f, int c, int K) {
vector<long long> pre(K + 2, 0), g(K + 1);
for (int s = 0; s <= K; s++) pre[s + 1] = (pre[s] + (s < (int)f.size() ? f[s] : 0)) % MOD;
for (int s = 0; s <= K; s++) {
int lo = max(0, s - c);
g[s] = (pre[s + 1] - pre[lo] + MOD) % MOD;
}
return g;
}
MOD = 998244353
# Nhân hai đa thức, chỉ giữ các hệ số bậc <= K (phép nhân chập cắt cụt)
def mul_trunc(a, b, K):
c = [0] * (K + 1)
for i, ai in enumerate(a[: K + 1]):
if ai == 0:
continue
for j, bj in enumerate(b[: K + 1 - i]):
c[i + j] = (c[i + j] + ai * bj) % MOD
return c
# Nhân f với (1 + x + ... + x^c), giữ bậc <= K, O(K) bằng tổng tiền tố:
# g[s] = f[s] + f[s-1] + ... + f[s-c]
def mul_bounded(f, c, K):
pre = [0] * (K + 2)
for s in range(K + 1):
pre[s + 1] = (pre[s] + (f[s] if s < len(f) else 0)) % MOD
return [(pre[s + 1] - pre[max(0, s - c)]) % MOD for s in range(K + 1)]
Đếm số cách chia kẹo có giới hạn cho bạn: bắt đầu từ rồi gọi mul_bounded(f, c_i, K) cho từng bạn, tổng .
Nghịch đảo chuỗi và lấy hệ số của
// Nghịch đảo chuỗi lũy thừa: tìm g với f * g = 1 (mod x^{K+1}), cần f[0] != 0 (mod p)
// Từ [x^n] (f * g) = 0 với n >= 1: g[n] = -(f[1] g[n-1] + ... + f[n] g[0]) / f[0]
vector<long long> inv_series(const vector<long long>& f, int K) {
vector<long long> g(K + 1, 0);
long long inv0 = power(f[0], MOD - 2);
g[0] = inv0;
for (int n = 1; n <= K; n++) {
long long s = 0;
for (int i = 1; i <= n && i < (int)f.size(); i++) s = (s + f[i] * g[n - i]) % MOD;
g[n] = (MOD - s) % MOD * inv0 % MOD;
}
return g;
}
// Các hệ số bậc 0..K của P(x) / Q(x): mul_trunc(P, inv_series(Q, K), K)
# Nghịch đảo chuỗi lũy thừa: tìm g với f * g = 1 (mod x^{K+1}), cần f[0] != 0 (mod p)
# Từ [x^n] (f * g) = 0 với n >= 1: g[n] = -(f[1] g[n-1] + ... + f[n] g[0]) / f[0]
def inv_series(f, K):
g = [0] * (K + 1)
inv0 = pow(f[0], MOD - 2, MOD)
g[0] = inv0
for n in range(1, K + 1):
s = 0
for i in range(1, min(n, len(f) - 1) + 1):
s += f[i] * g[n - i]
g[n] = (-s) % MOD * inv0 % MOD
return g
# Các hệ số bậc 0..K của P(x) / Q(x): mul_trunc(P, inv_series(Q, K), K)
Hệ số âm (như trong ) phải được nạp vào dưới dạng : các hàm trên giả định mọi hệ số nằm trong .
Độ phức tạp
| Phép toán | Thời gian | Bộ nhớ |
|---|---|---|
mul_trunc hai đa thức, cắt ở bậc |
||
mul_bounded (nhân với ) |
||
| Tích thừa số có giới hạn | ||
inv_series tới bậc |
||
| Nhân, nghịch đảo, , bằng NTT | ||
| Một hệ số của ở rất lớn (Bostan-Mori, ) |
Vòng inv_series ở bậc chỉ chạy qua các khác không, nên khi là đa thức bậc nhỏ, chi phí là , đúng bằng chạy trực tiếp dãy truy hồi. Khi tới trở lên và cả hai đa thức đều dày, bản quá chậm: chuyển sang NTT với lặp Newton.
⚠️ Lỗi thường gặp
- Quên cắt cụt: nhân đa thức mà giữ toàn bộ bậc làm kích thước phình lên , thời gian thành . Chỉ cần bậc thì cắt sau mỗi phép nhân.
- Hệ số âm modulo: phải lưu là ; trong C++,
(pre[s+1] - pre[lo]) % MODcó thể âm nếu thiếu+ MOD. - Chia cho : không phải chuỗi lũy thừa. Nếu mẫu chia hết cho , rút ra (dịch chỉ số) trước khi nghịch đảo.
- Nhầm OGF với EGF: đối tượng có nhãn (thứ tự thao tác, gán vị trí) mà dùng hàm sinh thường sẽ thiếu hệ số nhị thức; ngược lại dùng EGF cho đối tượng không nhãn sẽ thừa. Hỏi: đổi chỗ hai phần tử cùng loại có tạo cấu hình mới không?
- Đếm hai lần trong bài đối xứng: nửa trái của dãy đối xứng xuất hiện hai lần trong tổng, nên hàm sinh của nó phải lấy tại , không phải .
- Tràn số khi nhân:
a[i] * b[j]phải làlong longvà lấy modulo ngay; cộng dồn nhiều tích chưa modulo sẽ tràn với .
Biến thể / Mở rộng
- Tăng tốc bằng NTT: nhân đa thức , nghịch đảo bằng Newton , , bằng Newton. Xem FFT.
- Tích nhiều thừa số : lấy biến tích thành tổng (mỗi thừa số có số hạng), rồi lại; dùng cho đếm hoán vị theo số nghịch thế.
- Tổng lũy thừa : chính là với , đạo hàm logarit của tích.
- Hệ số của hàm sinh hữu tỷ ở lớn: Nhân ma trận hoặc Bostan-Mori; tìm lại từ các số hạng đầu bằng Berlekamp-Massey.
- Liên hệ: công thức đóng cho hệ số thường cần tổ hợp và bao hàm loại trừ (ví dụ khai triển ); đếm có đối xứng dùng Burnside và Polya.
Bài tập luyện
- Chia bánh (dhbb23ltt10_a): (Hard) Đếm cách chia chiếc bánh khác nhau sao cho có bạn nhận đúng chiếc; phần bù là nhân hệ số của tích các hàm sinh mũ .
- Di chuyển vị trí (thhv22_move): (Hard) Đếm dãy thao tác đưa các xạ thủ tới vị trí cho trước; đáp án là tích cắt cụt của các chuỗi (hàm sinh mũ theo số cặp bước thừa).
- Dãy đối xứng (icpc24mbk): (Very Hard) Đếm dãy đối xứng tổng chứa phần tử ; đếm phần bù bằng hàm sinh hữu tỷ có mẫu bậc rồi lấy một hệ số ở .
- Thợ săn x Liên lạc (icpc19nath): (Expert) Đếm cặp số cùng tổng đan dấu; đáp án là hệ số tự do của , khai triển bằng bao hàm loại trừ.
- Mangan đioxit (icpc21mtj): (Expert) Tính mọi tổng lũy thừa với qua đạo hàm logarit của , nhân và nghịch đảo bằng NTT.
- Bài khó nhất (icpc22regh): (Expert) Đếm hoán vị theo số nghịch thế với ràng buộc thứ tự; hàm sinh là tích , tính bằng rồi chuỗi.
- Đến giờ đấu bài rồi! (icpc23regi): (Expert) Đếm hoán vị với ; với mỗi độ dài chu trình, số cách gom chu trình thành khối là hệ số của một hàm sinh mũ.
Bình luận