HDU 2082 母函數模板題：字母組合價值計數

題意

26 個字母 A-Z 分別有 x₁…x₂₆ 個，價值 1…26。求價值和 ≤ 50 的不同單詞（組合，不考慮排列）數量。多測試用例。

母函數建模

普通生成函數：

G(x) = ∏_{i=1}^{26} (1 + xⁱ + x²ⁱ + … + x^{xᵢ·i})

展開後 xᵏ 的係數即為價值和為 k 的組合數。答案為 Σ_{k=1}^{50} coeff(k)。

代碼實現：多項式疊乘

#include <iostream>
#include <cstring>
using namespace std;
int c1[100], c2[100], a[30];
int main() {
    int T; cin >> T;
    while (T--) {
        for (int i=1;i<=26;i++) cin >> a[i];
        memset(c1, 0, sizeof(c1));
        memset(c2, 0, sizeof(c2));
        c1[0] = 1; // 初始多項式 = 1
        for (int i=1;i<=26;i++) { // 乘入第 i 個字母的多項式
            for (int j=0;j<=50;j++)
                for (int k=0; k<=a[i] && k*i+j<=50; k++)
                    c2[j + k*i] += c1[j];
            memcpy(c1, c2, sizeof(c2));
            memset(c2, 0, sizeof(c2));
        }
        int sum = 0;
        for (int i=1;i<=50;i++) sum += c1[i];
        cout << sum << endl;
    }
    return 0;
}

關鍵點

• 數組大小 51 足夠（最大價值 50）。
• 三重循環：外層 26 字母，中層當前多項式次數，內層取當前字母 0..xᵢ 個。
• 每輪結束 c2 → c1 並清零 c2。