ZOJ 2822 Sum of Different Primes：01 背包求質數組合數

ZOJ 2822 Sum of Different Primes

給定 n 和 k，求將 n 表示為 k 個不同質數之和的方案數。質數不重複使用，屬於 01 背包問題。

問題分析

• n ≤ 1120, k ≤ 14（因前 14 個質數和已超 1120）。
• 先用埃氏篩法求出 1120 以內所有質數（共 187 個）。
• DP 定義：`dp[i][j]` 表示用前若干質數，和為 i、恰好用 j 個質數的方案數。
• 轉移：對每個質數 p，從大到小更新 `dp[i][j] += dp[i-p][j-1]`。

代碼實現（C++）

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int MAXN = 1120;
const int MAXK = 15;

int dp[MAXN+1][MAXK];
vector<int> primes;

void sieve() {
    vector<bool> isPrime(MAXN+1, true);
    isPrime[0] = isPrime[1] = false;
    for(int i = 2; i*i <= MAXN; i++)
        if(isPrime[i])
            for(int j = i*i; j <= MAXN; j += i)
                isPrime[j] = false;
    for(int i = 2; i <= MAXN; i++)
        if(isPrime[i]) primes.push_back(i);
}

int main() {
    sieve();
    int n, k;
    while(scanf("%d%d", &n, &k) == 2 && (n || k)) {
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        for(int p : primes) {
            for(int i = n; i >= p; i--)
                for(int j = 1; j <= k; j++)
                    dp[i][j] += dp[i-p][j-1];
        }
        printf("%d\n", dp[n][k]);
    }
    return 0;
}

關鍵點

• 質數篩選上限 1120 足夠，因 n ≤ 1120。
• 01 背包必須逆序遍歷 i 和 j，避免重複使用同一質數。
• 多測試用例，每次重置 dp 數組。

複雜度

• 質數個數 ~187，狀態數 1120×14，轉移 O(187 × 1120 × 14) ≈ 2.9×10^6，極快。
• 空間 O(1120×14) ≈ 15k。

總結

經典 01 背包變體：物品為質數，重量=價值=質數值，限制物品數量為 k。逆序更新是關鍵。