BZOJ 2287 POJ Challenge 消失之物：分治 + 背包 DP 計算排除單項的方案數

問題描述

有 n 個物品，體積 wᵢ。對每個 i (1..n) 和每個容量 j (1..m)，輸出不使用第 i 個物品時，裝滿容量 j 的背包方案數（模 10）。n,m ≤ 2000。

分治 + 背包思想

第 i 個物品存在於時間區間 [1, i-1] 和 [i+1, n]。
構建線段樹，每個節點存儲一組物品。將每個物品插入到覆蓋其存在區間的線段樹節點中（共 O(log n) 個節點）。
對線段樹進行 DFS：進入節點時，將該節點物品合併到背包 DP 數組；到達葉子（對應某個 i）時，DP 數組即為排除第 i 物品的結果，輸出答案；退出節點時，回滾 DP（或傳遞副本）。

關鍵優化：避免回滾，傳遞 DP 副本

背包 DP 狀態 dp[j] = 方案數。合併物品 w：for(j=m;j>=w;j--) dp[j]=(dp[j]+dp[j-w])%10。
DFS 時傳遞 vector dp 為值參數（自動複製），子節點各自擁有副本，無需手動回滾。
復雜度：每個物品被合併 O(log n) 次，每次合併 O(m)，總 O(n m log n)。n,m=2000 時 ≈ 2000×2000×11 ≈ 4.4×10⁷，模 10 運極快，可通過。

代碼框架

struct Item { int l, r, w; }; // 存在區間 [l,r], 體積 w
vector seg[8000]; // 線段樹節點存物品列表
void addItem(int idx, int l, int r, int ql, int qr, int w) {
    if (ql <= l && r <= qr) { seg[idx].push_back({l,r,w}); return; }
    int mid = (l+r)>>1;
    if (ql <= mid) addItem(idx<<1, l, mid, ql, qr, w);
    if (qr > mid) addItem(idx<<1|1, mid+1, r, ql, qr, w);
}
void dfs(int idx, int l, int r, vector dp) {
    for (auto& it : seg[idx])
        for (int j = m; j >= it.w; j--)
            dp[j] = (dp[j] + dp[j-it.w]) % 10;
    if (l == r) {
        for (int j = 1; j <= m; j++) cout << dp[j];
        cout << '\n';
        return;
    }
    int mid = (l+r)>>1;
    dfs(idx<<1, l, mid, dp);
    dfs(idx<<1|1, mid+1, r, dp);
}
int main() {
    int n, m; cin >> n >> m;
    vector w(n+1);
    for (int i = 1; i <= n; i++) cin >> w[i];
    for (int i = 1; i <= n; i++) {
        if (i > 1) addItem(1, 1, n, 1, i-1, w[i]);
        if (i < n) addItem(1, 1, n, i+1, n, w[i]);
    }
    vector dp(m+1, 0); dp[0] = 1;
    dfs(1, 1, n, dp);
    return 0;
}

總結

BZOJ 2287 是分治背包（線段樹分治）的經典應用。將「排除單項」轉化為「物品在時間區間存在」，線段樹分配物品到節點，DFS 累積 DP。關鍵技巧：值參數傳遞 DP 數組自動回滾，代碼極簡、無錯誤。模 10 運算進一步加速。此模板適用於「動態增減物品查詢背包方案數」類問題。