题意

有 $n$ 个物品，体积分别为 $w_1,\dots,w_n$。对每个 $i$ 和 $x\in[1,m]$，问用除第 $i$ 个物品外的 $n-1$ 个物品填满容积 $x$ 的方案数（只输出末位数字）。$n,m\le 2000$。

思路

一句话本质：如果没有物品 $i$，方案数 = 全体物品方案数 − 包含物品 $i$ 的方案数。含 $i$ 的方案恰好可以在不含 $i$ 的方案上补一个 $i$ 得到，于是可以用递推一次性求出所有答案。

直接对每个 $i$ 分别跑 $n-1$ 个物品的背包行不行？

每个 $i$ 跑一次 0/1 背包是 $O(n^2m)$，$n,m\le 2000$ 时不可接受。必须找到更高效的方法。

全体物品的方案数 $f[j]$ 能告诉我们什么？

先跑一遍包含全部 $n$ 个物品的 0/1 背包计数，得到 $f[j]$：用全部物品凑出和 $j$ 的方案数。转移为：

$f[j]$ 是"用所有物品能凑出 $j$"的总方案数。但我们想要的是"不含第 $i$ 个物品"的方案数。

如何从 $f[j]$ 中扣除物品 $i$ 的贡献？

对于固定体积 $j$，$f[j]$ 中的方案分两类：一类不含 $i$（我们想要的），一类含 $i$。如果能算出"含 $i$ 的方案数"，用 $f[j]$ 减去它就是答案。

"含物品 $i$ 且和为 $j$"的方案数等于多少？

任何一个含 $i$ 且和为 $j$ 的方案，去掉 $i$ 后就变成"不含 $i$ 且和为 $j-w_i$"的方案。反过来，每个不含 $i$ 且和为 $j-w_i$ 的方案加上 $i$ 就得到一个含 $i$ 且和为 $j$ 的方案。两者一一对应。

设 $g[j]$ 表示不含物品 $i$ 时和为 $j$ 的方案数，那么含 $i$ 且和为 $j$ 的方案数就是 $g[j-w_i]$。于是：

当 $j<w_i$ 时，物品 $i$ 不可能被包含在 $j$ 中，所以 $f[j]$ 本身就不含 $i$，直接等于 $g[j]$。

为什么这个递推是安全的？

关键在于 $g[j-w_i]$ 依赖的是更小的容量，当我们按 $j$ 从小到大计算 $g[j]$ 时，$g[j-w_i]$ 已经在之前算好了。循环中 $g[0]=1$ 作为递推起点。

注意取模只需末位数字，所以用 %10 即可（减法时加 10 再取模防负数）。

最终对每个 $i$ 输出 $g[1]\dots g[m]$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2005;

int n, m;
int w[MAXN];         // 物品重量（体积）
// f[j] 表示用所有物品凑出和为 j 的方案数。
int f[MAXN];
// g[j] 表示不含当前物品时，凑出和为 j 的方案数。
int g[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
    }

    // 第一遍：正序 DP 求出包含所有物品的方案数 f[]。
    f[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= w[i]; j--) {
            f[j] = (f[j] + f[j - w[i]]) % 10;
        }
    }

    // 对每个物品 i，用 f[] - (包含 i 的方案) 得到不含 i 的方案数。
    for (int i = 1; i <= n; i++) {
        g[0] = 1;
        for (int j = 1; j <= m; j++) {
            if (j < w[i]) {
                g[j] = f[j];
            } else {
                // f[j] 中可能包含选了物品 i 的方案（即 g[j - w[i]]），
                // 从 f[j] 中减去这些方案得到不含 i 的方案数。
                g[j] = (f[j] - g[j - w[i]] + 10) % 10;
            }
        }
        for (int j = 1; j <= m; j++) {
            cout << g[j];
        }
        cout << '\n';
    }

    return 0;
}

复杂度

• 全物品 DP：$O(nm)$
• 每个 $i$ 的 $g$ 推出：$O(m)$，共 $O(nm)$
• 总时间复杂度：$O(nm)$，$n,m\le 2000$ 没有问题
• 空间复杂度：$O(m)$

总结

这题的明星技巧是"从全体方案中扣除某个物品的贡献"。它利用方案数在加/减物品时的对称关系，把 $n$ 次独立背包合并成一次全体背包 + $n$ 次线性递推。核心公式 $g[j]=f[j]-g[j-w_i]$ 本质上是正难则反：含 $i$ 的方案不好直接算，但可以由不含 $i$ 的方案补 $i$ 得到。