HDU 2079 選課時間——普通母函數求組合數

問題描述

有 k 種學分的課程，第 i 種學分為 `a[i]`，有 `b[i]` 門可選。選課總學分恰為 n，求選法數。課程同學分視為無區別。n ≤ 40, k ≤ 8, a ≤ 8, b ≤ 10。

母函數建模

第 i 類課程的生成函數：`(1 + x^{a[i]} + x^{2a[i]} + ... + x^{b[i]*a[i]})`。
總生成函數 = 所有類別生成函數乘積。
答案 = 乘積中 `x^n` 的係數。

DP 實現（多項式乘法）

• `c[j]` = 當前處理到的類別組合中，學分和為 j 的方案數。
• 初始 `c[0] = 1`，其餘 0。
• 對每類 i，用臨時數組 `tmp` 累加： `tmp[j + k*a[i]] += c[j]` 對所有 `j` 和 `k=0..b[i]`（`k*a[i]` 為選 k 門該學分課程的總學分）。
• 然後 `c = tmp`，繼續下一類。

代碼實現

#include 
using namespace std;
int c[45], tmp[45];
int a[11], b[11];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n, k; scanf("%d%d", &n, &k);
        for (int i = 1; i <= k; ++i) scanf("%d%d", &a[i], &b[i]);
        fill(c, c+n+1, 0);
        c[0] = 1;
        for (int i = 1; i <= k; ++i) {
            fill(tmp, tmp+n+1, 0);
            for (int j = 0; j <= n; ++j) if (c[j])
                for (int k = 0; k <= b[i] && j + k*a[i] <= n; ++k)
                    tmp[j + k*a[i]] += c[j];
            copy(tmp, tmp+n+1, c);
        }
        printf("%d\n", c[n]);
    }
    return 0;
}

關鍵點

• 母函數 = 多項式乘法：每類課程對應一個稀疏多項式，乘積係數即方案數。
• 雙重循環：外層遍歷當前已有學分 `j`，內層遍歷本類選擇門數 `k`（步長 `a[i]`）。
• 數據範圍小：n≤40, k≤8, b≤10，O(k·n·max(b)) ≈ 3200 操作，極快。
• 同學分無區別：母函數自然體現「選 k 門同學分課只有一種方式」。

複雜度

• 時間：O(T × k × n × max(b)) ≪ 1ms。
• 空間：O(n)。

總結

普通母函數經典入門題。將「有限重複物品選擇」建模為多項式乘法，DP 實現係數計算。掌握此模板，可解決所有「有限重複物品湊目標和方案數」問題。