多重集組合問題：n 種物品，第 i 種有 a[i] 個（同種不可區分），從中取 m 個的方案數模 M。本文從生成函數推導遞推、滑動窗口/前綴和優化至 O(nm)、邊界處理、模運算細節，提供完整 C 實現。
n 種物品，數量 a[0..n-1]；取 m 個；模數 Mmod Mn=3, a={1,2,3}, m=3 → 方案：(0,0,3)(0,1,2)(0,2,1)(1,0,2)(1,1,1)(1,2,0) → 6 種第 i 種物品生成函數：1 + x + x² + ... + x^{a[i]}
總生成函數：∏_{i=0}^{n-1} (1 + x + ... + x^{a[i]})
設 dp[i][j] = 前 i 種取 j 個方案數，則：
dp[i+1][j] = Σ_{k=0}^{min(j, a[i])} dp[i][j-k]
// 即：前 i+1 種取 j 個 = Σ (取 k 個第 i 種) × (前 i 種取 j-k 個)
觀察：
dp[i+1][j] = dp[i][j] + dp[i][j-1] + ... + dp[i][j-a[i]] dp[i+1][j-1] = dp[i][j-1] + dp[i][j-2] + ... + dp[i][j-1-a[i]] 相減得： dp[i+1][j] = dp[i+1][j-1] + dp[i][j] - dp[i][j-1-a[i]] (j-1-a[i] ≥ 0) dp[i+1][j] = dp[i+1][j-1] + dp[i][j] (j-1-a[i] < 0)
核心優化： 每個狀態 O(1) 計算，總複雜度 O(nm)。
#include <stdio.h>
#include <string.h>
#define MAX_N 1000
#define MAX_M 1000
int n, m, M;
int a[MAX_N];
int dp[MAX_N + 1][MAX_M + 1];
int multiset_combination() {
memset(dp, 0, sizeof(dp));
// 基例：取 0 個永遠有 1 種方案（全不取）
for (int i = 0; i <= n; i++) dp[i][0] = 1;
for (int i = 0; i < n; i++) {
for (int j = 1; j <= m; j++) {
// dp[i+1][j] = dp[i+1][j-1] + dp[i][j] - dp[i][j-1-a[i]]
long long val = dp[i+1][j-1] + dp[i][j];
if (j - 1 - a[i] >= 0) {
val -= dp[i][j - 1 - a[i]];
}
// 模運算修正負數
val = (val % M + M) % M;
dp[i+1][j] = (int)val;
}
}
return dp[n][m];
}
int main() {
n = 3; m = 3; M = 10000;
int a1[] = {1, 2, 3};
memcpy(a, a1, sizeof(a1));
printf("result = %d\n", multiset_combination()); // 6
return 0;
}
i\j 0 1 2 3 0 1 1 1 1 (第0種a=1: 取0/1個) 1 1 2 3 3 (第1種a=2: 累加前綴和) 2 1 3 6 6 (第2種a=3: 結果dp[3][3]=6)
// C 語言 % 運算符對負數結果為負或實現定義 // 必須修正至 [0, M-1] val = (val % M + M) % M; // 標準寫法 // 或 if (val < 0) val += M; else if (val >= M) val -= M; // 單次加減足夠，因 |val| < 2M
int dp[MAX_M + 1]; // 僅保留當前行
memset(dp, 0, sizeof(dp));
dp[0] = 1;
for (int i = 0; i < n; i++) {
// 需要前一行值，故需臨時數組或逆序技巧
// 此處前綴和依賴 dp[i][*] 故需兩行滾動
static int new_dp[MAX_M + 1];
new_dp[0] = 1;
for (int j = 1; j <= m; j++) {
long long val = new_dp[j-1] + dp[j];
if (j - 1 - a[i] >= 0) val -= dp[j - 1 - a[i]];
new_dp[j] = (val % M + M) % M;
}
memcpy(dp, new_dp, sizeof(new_dp));
}
return dp[m];
| 變體 | 修改點 | 應用 |
|---|---|---|
| 輸出具體方案 | 記錄選擇數 choice[i][j] 回溯 | 組合生成 |
| 無限制多重集 | a[i] = INF，退化為組合數 C(n+m-1, m) | 星條定理 |
| 不同物品必選至少 1 個 | 預先各取 1 個，m -= n，a[i]-- | 分配問題 |
| 大模數/質數模 | 用長整型/模逆元優化除法 | 組合數學競賽 |
| 算法 | 時間 | 空間 | 備註 |
|---|---|---|---|
| 朴素三重循環 | O(nm·max(a)) | O(nm) | a[i] 大時不可用 |
| 前綴和優化（推薦） | O(nm) | O(nm) / O(m) | 通用標準解 |
| 生成函數 FFT | O(m log m log n) | O(m) | 超大 m (10⁵+) 需 NTT |
多重集組合數問題展示了「前綴和優化 DP 轉移」的教科書級應用：將 Σ_{k} dp[j-k] 轉化為 dp[j-1] + dp[j] - dp[j-1-a]，將內層循環完全消除。這種「滑動窗口/前綴和」技巧同樣適用於完全背包方案數、受限組合計數、滑動窗口統計等問題。掌握遞推關係的代數變形能力，是從「會寫 DP」進階到「會優化 DP」的關鍵一步。
