POJ 3046 Ant Counting：分組背包計數方案數

問題描述

T 類螞蟻，第 i 類有 N_i 隻。從中選若干隻組成群體，群體大小在 [S, B] 之間。不同類螞蟻不可區分，同類選擇數量不同視為不同群體。求方案數模 1,000,000。

解題思路

分組背包計數：每類螞蟻為一組，可選 0 到 N_i 隻。`dp[j]` 表示選 j 隻螞蟻的方案數。初始 `dp[0]=1`。對每類，對 j 從總數遞減到 0，對 k=1..N_i，若 `j>=k` 則 `dp[j] = (dp[j] + dp[j-k]) % MOD`。最後累加 `dp[S..B]`。

代碼實現 (C++)

#include 
using namespace std;
const int MOD = 1000000;
const int MAXN = 100005;
int dp[MAXN], cnt[1005];

int main() {
    int T, A, S, B;
    while (cin >> T >> A >> S >> B) {
        fill(cnt, cnt+T+1, 0);
        for (int i = 0; i < A; ++i) {
            int type; cin >> type; ++cnt[type];
        }
        fill(dp, dp+A+1, 0);
        dp[0] = 1;
        for (int i = 1; i <= T; ++i) {
            for (int j = A; j >= 0; --j) {
                for (int k = 1; k <= cnt[i]; ++k) {
                    if (j >= k) dp[j] = (dp[j] + dp[j-k]) % MOD;
                }
            }
        }
        int ans = 0;
        for (int i = S; i <= B; ++i) ans = (ans + dp[i]) % MOD;
        cout << ans << endl;
    }
    return 0;
}

複雜度分析

• 時間複雜度：O(T * A * max(N_i))，A ≤ 1000，T ≤ 1000，N_i ≤ 100，約 10^7 操作。
• 空間複雜度：O(A)。

總結

分組背包計數方案數，注意內層循環順序：j 遞減保證 01 特性（每類螞蟻只能用一次組合），k 循環枚舉選擇數量。模 1,000,000 取模。