BZOJ 2023 [Usaco 2005 Nov] Ant Counting — DP + 滾動陣列 + 前綴和優化

題目

T≤1000 個螞蟻家族，第 i 家族 N_i≤100 隻。同家族螞蟻不可區分。選 S..B 隻螞蟻出行（1≤S≤B≤總數），求不同組隊方案數（模 1,000,000）。

DP 定義

f[i][j]：前 i 個家族，選 j 隻螞蟻的方案數。
轉移：f[i][j] = Σ_{k=0}^{min(N_i, j)} f[i-1][j-k]。

優化 1：滾動陣列

i 僅依賴 i-1，用 f[2][MAX] 交替。

優化 2：前綴和將內層循環 O(N_i) → O(1)

設 g[i][j] = Σ_{t=0}^j f[i][t]，則：
f[i][j] = g[i-1][j] - (j > N_i ? g[i-1][j-N_i-1] : 0)。
同步維護 g 即可。

完整 C++ 代碼

#include 
using namespace std;
const int MOD = 1000000;
const int MAXN = 1000005;  // 總螞蟻數上限

int n, m, S, B;
int cnt[1005];             // 每家族數量
int f[2][MAXN], g[2][MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> S >> B;  // 原題輸入 T A S B，此處對應
    for (int i=1;i<=m;++i) {
        int fam; cin >> fam;
        cnt[fam]++;
    }
    f[0][0] = g[0][0] = 1;
    for (int i=1;i<=B;++i) g[0][i] = 1;

    int cur = 0;
    for (int i=1;i<=n;++i) {
        cur ^= 1;
        fill(f[cur], f[cur]+B+1, 0);
        fill(g[cur], g[cur]+B+1, 0);
        for (int j=1;j<=B;++j) {
            if (j > cnt[i])
                f[cur][j] = (g[cur^1][j] - g[cur^1][j-cnt[i]-1] + MOD) % MOD;
            else
                f[cur][j] = g[cur^1][j] % MOD;
            g[cur][j] = (g[cur][j-1] + f[cur][j]) % MOD;
        }
    }
    int ans = 0;
    for (int i=S;i<=B;++i) ans = (ans + f[cur][i]) % MOD;
    cout << ans << '\n';
    return 0;
}

複雜度

• 時間：O(T·B)，B ≤ 10⁵，T ≤ 1000 但實際總螞蟻數 ≤ 10⁵，極快。
• 空間：O(B)，兩個長度 B+1 陣列。

關鍵點總結

1. 「不可區分」→ 組合數 DP，而非排列。
2. 前綴和優化是經典「分組背包 O(V·N) → O(V)」技巧。
3. 模數 1e6 非質數，僅做加減乘，無需逆元。