HDU 2082 找單詞：普通型母函數解決組合計數問題

題目大意

給定 26 個大寫字母 A-Z 的可用數量 x1..x26（各 ≤ 20），字母價值為其序號（A=1, B=2, ..., Z=26）。求：能組成多少個總價值 ≤ 50的單詞。單詞不考慮字母順序（視為組合），即多重集合選擇問題。

核心方法：普通型母函數

因為不考慮排列順序，屬於組合問題，使用普通型母函數（Ordinary Generating Function）。每種字母對應一個多項式，係數代表選擇該字母若干個的方案數，指數代表價值總和。

單一字母母函數

字母 i（價值 i）有 cnt 個可用，其母函數為：

G_i(x) = 1 + x^i + x^{2i} + ... + x^{cnt*i}

• 1 代表選 0 個（價值 0）。
• x^{k*i} 代表選 k 個（價值 k*i），係數為 1（同種字母無區分）。

總母函數

26 個字母母函數相乘：

G(x) = ∏_{i=1}^{26} G_i(x)

展開後，x^v 的係數即為總價值為 v 的單詞組合數。答案為 v=1..50 係數之和（v=0 對應空單詞，不計入）。

多項式乘法實現

維護兩個係數陣列 c1[0..50]（當前結果）、c2[0..50]（暫存）。初始 c1[0]=1。對每個字母 i=1..26：

for j = 0..50:
    for k = 0..cnt_i, while k*i + j <= 50:
        c2[k*i + j] += c1[j]
c1 = c2; clear c2

• 外層 j 遍歷當前多項式非零項。
• 中層 k 遍歷選擇當前字母的個數（0 到 cnt_i）。
• 新指數 k*i + j，係數累加 c1[j]。
• 指數上限 50，超出忽略。

範例驗證

輸入：1 1 1 0 ...（A,B,C 各 1 個，價值 1,2,3）

母函數：(1+x)(1+x^2)(1+x^3) = 1 + x + x^2 + 2x^3 + x^4 + x^5 + x^6

係數和（1..6）= 1+1+1+2+1+1+1 = 7，符合樣例輸出。

完整程式碼

#include <iostream>
using namespace std;

int c1[55], c2[55], arr[30];

void Init() {
    for (int i = 0; i < 55; i++) c1[i] = c2[i] = 0;
}

int main() {
    int n; cin >> n;
    while (n--) {
        Init();
        for (int i = 1; i <= 26; i++) cin >> arr[i];
        c1[0] = 1;
        for (int i = 1; i <= 26; i++) {
            for (int j = 0; j <= 50; j++) {
                for (int k = 0; k <= arr[i] && k*i + j <= 50; k++) {
                    c2[k*i + j] += c1[j];
                }
            }
            for (int j = 0; j <= 50; j++) {
                c1[j] = c2[j];
                c2[j] = 0;
            }
        }
        int ret = 0;
        for (int i = 1; i <= 50; i++) ret += c1[i];
        cout << ret << endl;
    }
    return 0;
}

複雜度分析

• 26 字母 × 51 指數 × 最大 20 迴圈 ≈ 26 × 51 × 20 ≈ 2.6 萬次操作，極快。
• 空間 O(50)，常數級。

延伸：指數型母函數

若考慮字母順序（排列問題），需使用指數型母函數，每項係數除以階乘 k!。本題為組合問題，故用普通型。