题意
题解
考虑 DP，设 $f(i)$ 为装满容量为 $i$ 的背包的方案数，这个很容易求。
设 $g(i, j)$ 为不用第 $i$ 个物品，装满容量为 $j$ 的背包的方案数。
当 $j < w[i]$ 时，$g(i, j) = f(j)$；
当 $j \geq w[i]$ 时，我们用 总方案数 减 选的方案数来计算：$g(i, j) = f(j) - g(i, j - w[i])$。
代码
#include <algorithm>
#include <iostream>
#define TPT "%lld"
#define RTP(x) scanf(TPT, &x)
using namespace std;
using tp = long long;
constexpr bool __TESTS__ = 0;
constexpr tp Hat_N = 2e3 + 3, Hat_M = 2e3 + 3;
tp v[Hat_N], f[Hat_N], tar[Hat_N][Hat_M];
signed __CORE__() {
tp n, m;
*f = 1;
scanf(TPT TPT, &n, &m);
for_each(tar + 1, tar + n + 1, [](tp*&& x) { *x = 1; });
for_each(v + 1, v + n + 1, [&](tp& x) {
RTP(x);
for (tp j = m; j >= x; --j) {
f[j] = (f[j] + f[j - x]) % 10;
}
});
for (tp i = 1; i <= n; ++i) {
for (tp j = 1; j <= m; ++j) {
tar[i][j] = j < v[i] ? f[j] : (f[j] - tar[i][j - v[i]] + 10) % 10;
cout << tar[i][j];
}
cout << '\n';
}
return 0;
}
signed __PRE__() {
return 0;
}
signed main() {
static tp p = __PRE__(), t = 1, r = scanf(__TESTS__ ? "%lld" : "", &t);
return t-- && (main() || __CORE__()) ? -1 : p;
}
// \
╭───────────────────────────────────────────────────────────╮ \
│ This Code Was Created By RBTree (https://rbtr.ee) │ \
╰───────────────────────────────────────────────────────────╯
//