動態規劃：抗震救災志願者分組 (每組人數為質數) 方案數

問題模型

將 n (2 ≤ n ≤ 150) 個無差別志願者分成若干組，每組人數必須為質數，求分組方案數。順序不分 (即整數分拆，部分限制為質數)。

動態規劃解法

• 狀態：dp[i] 表示人數和為 i 的合法分組方案數。
• 轉移：枚舉質數 p，dp[i] += dp[i-p] (為避免重複計數，外層循環質數，內層循環人數，即完全背包「組合數」模板)。
• 初始：dp[0] = 1 (空分組 1 種)。

完整代碼 (C++)

#include 
using namespace std;
const int MAXN = 150;
int main() {
    vector primes;
    vector isPrime(MAXN + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i <= MAXN; ++i) {
        if (isPrime[i]) {
            primes.push_back(i);
            for (int j = i * i; j <= MAXN; j += i) isPrime[j] = false;
        }
    }

    vector dp(MAXN + 1, 0);
    dp[0] = 1;
    for (int p : primes) {           // 外層質數：保證組合不重複
        for (int i = p; i <= MAXN; ++i) { // 內層人數：完全背包
            dp[i] += dp[i - p];
        }
    }

    int C; cin >> C;
    while (C--) {
        int n; cin >> n;
        cout << dp[n] << endl;
    }
    return 0;
}

樣例驗證

• n=3：{3} → 1
• n=4：{2,2} → 1
• n=5：{5}, {2,3} → 2

符合樣例輸出。

複雜度

• 質數篩選 O(N log log N)，DP O(N × π(N)) ≈ 150 × 35 = 5250，極快。
• 結果可能超過 32 位整數，用 long long (64位) 或大整數 (n=150 時約 10^10 級)。