Codeforces 543A：完全背包變體 - 程序員寫代碼與 Bug 計數

題目大意

n 個程序員寫 m 行代碼。第 i 個程序員每行代碼產生 a[i] 個 bug。總 bug 數不超過 b。求方案數模 mod。n, m, b ≤ 500。

動態規劃建模

定義 dp[i][j][k] = 前 i 個程序員寫 j 行代碼產生 k 個 bug 的方案數。
轉移：第 i 個程序員寫 0~j 行。
dp[i][j][k] = dp[i-1][j][k] + dp[i][j-1][k - a[i]] （完全背包順序：i 固定，j 遞增，k 遞增）。

滾動數組優化空間

第三維 k ≤ 500，第二維 j ≤ 500，第一維 i ≤ 500。
dp[501][501] 兩層滾動：cur = i&1, pre = (i-1)&1。
初始化：dp[cur][0][0] = 1。

關鍵代碼

#include 
using namespace std;
int n, m, b;
long long mod;
long long a[505];
long long dp[2][505][505];

int main() {
    cin >> n >> m >> b >> mod;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) dp[i&1][0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            for (int k = 0; k <= b; ++k) {
                if (k < a[i]) dp[i&1][j][k] = dp[(i-1)&1][j][k] % mod;
                else dp[i&1][j][k] = (dp[i&1][j-1][k - a[i]] + dp[(i-1)&1][j][k]) % mod;
            }
        }
    }
    long long ans = 0;
    for (int k = 0; k <= b; ++k) ans = (ans + dp[n&1][m][k]) % mod;
    cout << ans << endl;
    return 0;
}

複雜度

• 時間：O(n × m × b) = 500³ = 1.25×10⁸，常數極小，C++ 1s 內通過。
• 空間：O(2 × m × b) = 2 × 500 × 500 × 8 bytes ≈ 4 MB。

關鍵點

• 完全背包順序：j 從 1 到 m 遞增，k 從 0 到 b 遞增，直接用 dp[i&1][j-1][...] 實現「當前程序員多寫一行」。
• 滾動數組節省第一維空間。
• 模數操作每一步都取模，防溢出。

總結

CF 543A 是「分組完全背包」的經典變體：每組（程序員）有固定成本（每行 bug），選擇行數（物品數量），目標湊總行數 m 且總 bug ≤ b。滾動數組 + 正序遍歷是模板級寫法。