母函數入門：從組合計數到整數拆分的生成函數方法

母函數入門：從組合計數到整數拆分的生成函數方法

母函數（Generating Function）是組合數學中將序列編碼為形式冪級數係數的工具。通俗理解：一個多項式（或冪級數）的各項係數恰好對應目標序列的每一項。

核心思想

對於第 i 類物品有 k_i 個，其選擇方案生成函數為：

(x^0 + x^1 + ... + x^{k_i})

系數均為 1，因為同類物品選 j 件只有 1 種方式。
所有類別相乘，x^m 的係數即為選 m 件物品的總方案數——這正是組合計數的乘法原理在生成函數中的體現。

普通型與指數型

• 普通型：G(x) = Σ a_n x^n，用於組合選擇、整數拆分（順序無關）。
• 指數型：E(x) = Σ a_n x^n / n!，用於排列問題（順序有關）。

經典框架代碼（HDU 1028 風格）

// a[] 保存當前多項式係數，b[] 作為臨時數組
for (int i = 2; i <= n; i++) {
    for (int j = 0; j <= n; j++)
        for (int k = 0; k + j <= n; k += i) // 步長為 i，對應 x^0, x^i, x^{2i}...
            b[k + j] += a[j];
    for (int j = 0; j <= n; j++) {
        a[j] = b[j];
        b[j] = 0;
    }
}

關鍵行 k += i 體現了「每次增加 i 件該類物品」的生成函數乘法。

應用場景

1. 有限背包/組合計數：每類物品數量有限，直接套用上述框架。
2. 整數拆分：將 n 拆分為若干正整數之和的方案數，對應無限背包母函數。
3. 方程非負整數解：x1+x2+...+xk=n 的解數，即 (1+x+x²+...)^k 中 x^n 係數。

學習建議

「根據題意，仔細分析，建立關係。」—— 母函數的關鍵在於正確建模每個約束對應的生成函數因子，乘法展開後提取係數即為答案。

掌握母函數思維，能將許多複雜組合問題轉化為多項式乘法，配合 DP 實現係數計算，是解決計數類問題的利器。