题解：P13659 [CERC 2020] Storage Problems

· · 题解

\mathscr{Description}

对于第 i 个黑帮分子，以及每个 j(1\le j<n)，我们要求出在储藏室中恰好有 j 个物品，并且这些物品的总重量不超过 k，但加上 w_i 后超过 k 的不同子集的数量。

\mathscr{Body}

我们要求的是不包含 i 的大小为 j、总重为 s 的子集数：

\text{ans}_{i, j} = \sum_{s = \max(0,\, K-w_i+1)}^{K}

所以我们需要计算 不包含某个物品的背包方案数。

容易想到“退背包”技巧。如果我们先算出 所有物品 的背包计数 f_{m,s}（选 m 个物品总重 s 的方案数），那么去掉物品 i 的方案数可以用 退背包 得到。

:::info[“退背包”定义]{close}

时间复杂度为 \mathcal{O}(N^2K)。

\mathscr{Code}


/*
    author: Nimbunny
    powered by c++14
*/

#include <bits/stdc++.h>
#define endl '\n'
#define pi pair<int, int>
#define int long long
// #pragma GCC optimize(2)

using namespace std;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const int mod = 167772161;
const int N = 405;
int n, k, a[N], ans[N][N];
int f[N][N]; // f[i][j] 表示从所有物品中选 i 个，总重量 j 的方案数
int g[N][N]; // 临时退背包数组

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    // 全局背包
    f[0][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = n; j >= 1; j--)
            for (int t = k; t >= a[i]; t--)
                f[j][t] = (f[j][t] + f[j - 1][t - a[i]]) % mod;
    // 对每个 i 做退背包
    for (int i = 1; i <= n; i++) {
        memcpy(g, f, sizeof f); // 复制 f 到 g
        // 退掉物品 i
        for (int j = 1; j <= n; j++)
            for (int t = a[i]; t <= k; t++)
                g[j][t] = (g[j][t] - g[j - 1][t - a[i]] + mod) % mod;
        for (int j = 1; j < n; j++) {
            int low = max(0ll, k - a[i] + 1);
            if (low > k) {
                ans[i][j] = 0;
                continue;
            }
            for (int t = low; t <= k; t++)
                ans[i][j] = (ans[i][j] + g[j][t]) % mod;
        }
    }
    for (int i = 1; i <= n; i++, cout << endl)
        for (int j = 1; j < n; j++)
            cout << ans[i][j] << " ";
    return 0;
}