HDU 1028 Ignatius and the Princess III：母函數求整數分拆數

題目大意

給定正整數 N (≤120)，求將 N 表示為若干正整數之和的不同方案數（順序不計，即 3+1 與 1+3 視為同一分拆）。例如 N=4 有 5 種：4, 3+1, 2+2, 2+1+1, 1+1+1+1。

母函數原理

每個整數 i 可取 0,1,2,... 個，對應生成函數 1 + x^i + x^{2i} + ...。所有整數的生成函數乘積為：

G(x) = (1+x+x^2+...)(1+x^2+x^4+...)(1+x^3+x^6+...)...

x^N 的係數即為答案。計算時只需保留 x^0 ~ x^N 的係數。

算法實現：多項式乘法模擬

• c[i] 存儲當前乘積中 x^i 的係數。
• 初始 c[i]=1（對應第一個因式 1+x+x^2+...）。
• 對每個 k = 2..N，將 c 與 (1+x^k+x^{2k}+...) 相乘：

for (int k = 2; k <= n; k++) {
    for (int i = 0; i <= n; i++)       // 遍歷 c 中現有項
        for (int j = 0; i+j <= n; j += k) // 遍歷新因式中項
            temp[i+j] += c[i];
    c = temp; temp 清零;
}

完整代碼

#include <iostream>
using namespace std;
int c[121], temp[121];
int main() {
    int n;
    while (cin >> n) {
        for (int i = 0; i <= n; i++) c[i] = 1, temp[i] = 0;
        for (int k = 2; k <= n; k++) {
            for (int i = 0; i <= n; i++)
                for (int j = 0; i+j <= n; j += k)
                    temp[i+j] += c[i];
            for (int i = 0; i <= n; i++) c[i] = temp[i], temp[i] = 0;
        }
        cout << c[n] << endl;
    }
    return 0;
}

模板版本（更通用）

const int MAXN = 10001;
int c1[MAXN], c2[MAXN];
while (cin >> nNum) {
    for (int i=0; i<=nNum; i++) c1[i]=1, c2[i]=0;
    for (int i=2; i<=nNum; i++)
        for (int j=0; j<=nNum; j++)
            for (int k=0; k+j<=nNum; k+=i)
                c2[j+k] += c1[j];
    for (int j=0; j<=nNum; j++) c1[j]=c2[j], c2[j]=0;
    cout << c1[nNum] << endl;
}

手動模擬驗證 (N=4)

1. 初始 c=[1,1,1,1,1] (1+x+x^2+x^3+x^4)
2. 乘 (1+x^2+x^4)：c=[1,1,2,2,3]
3. 乘 (1+x^3)：c=[1,1,2,3,4]
4. 乘 (1+x^4)：c=[1,1,2,3,5] → c[4]=5 ✓

總結

母函數將組合計數轉化為多項式乘法，通過數組模擬係數更新，時間複雜度 O(N^2)，對 N≤120 足夠。關鍵在於理解「每個數可取任意多個」對應幂級數因子，以及係數累加的物理意義。