Wiki › Thuật toán › Toán học › Hàm sinh (Generating Functions)

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.

huunguyen huunguyen Updated Tháng 11. 16, 2026 Đọc 14 phút 3 lượt xem

Hàm sinh (generating function) là cách "đóng gói" cả một dãy số a0,a1,a2,… vào một đối tượng duy nhất: chuỗi lũy thừa hình thức A(x)=a0+a1x+a2x2+…. Ta không thay số vào x; xk chỉ là "nhãn" đánh dấu vị trí thứ k. 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 [xN]P(x)Q(x), tức một dãy truy hồi tuyến tính, rồi lấy hệ số ở N tới 1018; (3) với bậc tới 105 hoặc 106, kết hợp NTT để nhân, nghịch đảo, lấy ln và exp của chuỗi trong O(NlogN). Trang này tập trung vào tư duy và các phép toán O(K2) hoặc O(nK) cơ bản; phần tăng tốc bằng NTT xem trang FFT.

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

Ký hiệu [xk]A(x) là hệ số của xk trong A(x).

Bổ đề nhân (quy tắc nhân của phép đếm). Nếu A(x)=∑aixi đếm số cách chọn một đối tượng loại 1 có "trọng lượng" i, và B(x)=∑bjxj đế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 k là

[xk]A(x)B(x)=∑i+j=kaibj.

Chứng minh: khai triển tích, mỗi cặp (i,j) góp đúng một số hạng aibjxi+j; gom theo lũy thừa của x là xong. Vì xi·xj=xi+j 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
1,1,1,… 11−x chọn một số ≥0 bất kỳ
c+1 số 1, rồi toàn 0 1+x+…+xc=1−xc+11−x chọn một số trong [0,c]
0,1,1,1,… x1−x chọn một số nguyên dương
an=(n+m−1m−1) 1(1−x)m chia n viên kẹo cho m bạn
1,r,r2,… 11−rx
1,1,2,3,5,… (Fibonacci) 11−x−x2 lát dải 1×n bằng ô dài 1 và 2

Các phép biến đổi. Nhân với xm: dịch dãy sang phải m chỗ. Nhân với 11−x: lấy tổng tiền tố ([xn]A1−x=a0+…+an). Nhân với (1−x): lấy hiệu kề. Nhân với 1+x+…+xc: tổng của c+1 hệ số liên tiếp, làm được trong O(K) bằng tổng tiền tố thay vì O(Kc).

Hàm sinh hữu tỷ tương đương dãy truy hồi tuyến tính. Nếu A(x)=P(x)Q(x) với Q(x)=1−q1x−…−qdxd và degP<d, thì từ A·Q=P, so sánh hệ số xn với n≥d:

an=q1an−1+q2an−2+…+qdan−d.

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 PQ với degQ nhỏ thì lấy hệ số thứ N=1018 đượ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 K, ta chia chuỗi trực tiếp: với Q(0)≠0, hệ số của G=1/Q thỏa [xn](Q·G)=0 với mọi n≥1, nên

g0=1q0,gn=−1q0∑i=1nqign−i.

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 A^(x)=∑anxnn!. Tích hai EGF cho n!·[xn]A^B^=∑k(nk)akbn−k: hệ số nhị thức tự động đếm cách chia nhãn cho hai phần. Ví dụ, số cách xếp T thao tác khi người thứ i làm ci thao tác là hệ số đa thức T!c1!c2!⋯, chính là T! nhân hệ số của tích các EGF xcici!.

Mẹo phần bù và cắt cụt. Đếm "có ít nhất một phần tử bằng K" thường quy về đếm phần bù "không phần tử nào bằng K": hàm sinh một phần tử đổi từ x1−x thành x1−x−xK. Và vì chỉ cần hệ số tới bậc K, mọi phép nhân đều làm theo modulo xK+1: 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 s 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 s?

Theo bổ đề nhân, đáp án là các hệ số của

F(x)=(1+x+x2)(1+x)(1+x+x2+x3).

Nhân lần lượt từng thừa số. Bước 1: (1+x+x2)(1+x)=1+2x+2x2+x3. Bước 2 nhân với 1+x+x2+x3 bằng tổng trượt cửa sổ độ dài 4 (gs=fs+fs−1+fs−2+fs−3):

 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
s 0 1 2 3 4 5 6
số cách [xs]F 1 3 5 6 5 3 1

Kiểm chứng s=3 bằng liệt kê (c1,c2,c3): (0,0,3),(0,1,2),(1,0,2),(1,1,1),(2,0,1),(2,1,0), đúng 6 cách. Tổng các hệ số là 3·2·4=24=F(1): thay x=1 đếm mọi cách không quan tâm tổng.

Chia chuỗi: với Q(x)=1−x−x2 (nạp vào modulo p là q=[1,p−1,p−1]), công thức gn=−(q1gn−1+q2gn−2) cho gn=gn−1+gn−2, và 11 hệ số đầu của 1/Q là 1,1,2,3,5,8,13,21,34,55,89: đúng dãy Fibonacci.

Cài đặt

Các hàm dưới đây làm việc theo modulo p=998244353 và cắt mọi kết quả ở bậc K.

Nhân đa thức cắt cụt và nhân với 1+x+…+xc
C++
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;
}
Python
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 n bạn: bắt đầu từ f=[1,0,…,0] rồi gọi mul_bounded(f, c_i, K) cho từng bạn, tổng O(nK).

Nghịch đảo chuỗi và lấy hệ số của P/Q
C++
// 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)
Python
# 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ư −1 trong 1−x−x2) phải được nạp vào dưới dạng p−1: các hàm trên giả định mọi hệ số nằm trong [0,p).

Độ phức tạp

Phép toán Thời gian Bộ nhớ
mul_trunc hai đa thức, cắt ở bậc K O(K2) O(K)
mul_bounded (nhân với 1+…+xc) O(K) O(K)
Tích n thừa số có giới hạn O(nK) O(K)
inv_series tới bậc K O(K·min(K,degQ)) O(K)
Nhân, nghịch đảo, ln, exp bằng NTT O(KlogK) O(K)
Một hệ số của P/Q ở N rất lớn (Bostan-Mori, d=degQ) O(d2logN) O(d)

Vòng inv_series ở bậc n chỉ chạy qua các qi khác không, nên khi Q là đa thức bậc d nhỏ, chi phí là O(Kd), đúng bằng chạy trực tiếp dãy truy hồi. Khi K tới 105 trở lên và cả hai đa thức đều dày, bản O(K2) 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 n đa thức mà giữ toàn bộ bậc làm kích thước phình lên ∑ci, thời gian thành O((∑ci)2). Chỉ cần bậc ≤K thì cắt sau mỗi phép nhân.
  • Hệ số âm modulo: −1 phải lưu là p−1; trong C++, (pre[s+1] - pre[lo]) % MOD có thể âm nếu thiếu + MOD.
  • Chia cho Q(0)=0: 1x không phải chuỗi lũy thừa. Nếu mẫu chia hết cho xm, rút xm 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 x2, không phải x.
  • Tràn số khi nhân: a[i] * b[j] phải là long long và lấy modulo ngay; cộng dồn nhiều tích chưa modulo sẽ tràn với p≈109.

Biến thể / Mở rộng

  • Tăng tốc bằng NTT: nhân đa thức O(KlogK), nghịch đảo bằng Newton R←R(2−QR), lnF=∫F′/F, exp bằng Newton. Xem FFT.
  • Tích nhiều thừa số 1−xv1−x: lấy ln biến tích thành tổng (mỗi thừa số ln(1−xv)=−∑txvt/t có K/v số hạng), rồi exp lại; dùng cho đếm hoán vị theo số nghịch thế.
  • Tổng lũy thừa ∑iaij: chính là −xP′(x)/P(x) với P(x)=∏(1−aix), đạo hàm logarit của tích.
  • Hệ số của hàm sinh hữu tỷ ở N lớn: Nhân ma trận hoặc Bostan-Mori; tìm lại Q 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 (1−x10)m(1−x)−m); đế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 N chiếc bánh khác nhau sao cho có bạn i nhận đúng i chiếc; phần bù là N! nhân hệ số xN của tích các hàm sinh mũ ∑c≠ixc/c!.
  • Di chuyển vị trí (thhv22_move): (Hard) Đếm dãy T 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 ∑kxkk!(k+ai)! (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 N≤1018 chứa phần tử K; đếm phần bù bằng hàm sinh hữu tỷ có mẫu bậc 2K+2 rồi lấy một hệ số ở N.
  • 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 E(x)E(1/x)(D(x)D(1/x))n−1, 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 ∑aij với j≤105 qua đạo hàm logarit −xP′/P của P=∏(1−aix), 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 ∏1−xv1−x, tính bằng ln rồi exp chuỗi.
  • Đến giờ đấu bài rồi! (icpc23regi): (Expert) Đếm hoán vị p với pk=a; 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 exp một hàm sinh mũ.
Trang này có hữu ích không? Đăng nhập để trả lời

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0