Link

是真的需要补一补dp

Sol

首先还是可以想到经典的背包计数。那么就是设 $f[i][j]$ 表示放前$i$个物品，体积为$j$的方案数。转移非常简单，$f[i][j] = f[i-1][j] + f[i - 1][j - w[i]]$ 。边界条件$f[0][0] = 1$

现在我们要考虑不放第$i$个物品体积为$x$的方案数，设这个为$g[i][j]$。那么不放$i$可以由两种情况。假如当前的体积$j < w[i]$，那么我们怎么也不可能放第$i$个物品，$g[i][j] = f[i][j]$ 。假如当前的体积$j \geq w[i]$， 那么方案数就是所有物品放出体积为$j$的背包的方案数减去不放第$i$个物品凑出体积为$j-w[i]$的背包的方案数

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int SIZE = 2e3 + 5;

int n, m;
int w[SIZE], f[SIZE][SIZE], c[SIZE][SIZE];

namespace ae86 {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using ae86::read;

signed main() {
    // freopen("code.in", "r", stdin);
    n = read(), m = read();
    for (int i = 1; i <= n; ++ i) w[i] = read();
    f[0][0] = 1;
    for (int i = 1; i <= n; ++ i) {
        for (int j = 0; j <= m; ++ j) {
            f[i][j] = (f[i][j] + f[i - 1][j]) % 10;
            if (j >= w[i]) f[i][j] = (f[i][j] + f[i - 1][j - w[i]]) % 10;
        }
    }
    for (int i = 0; i <= m; ++ i) c[0][i] = 1;
    for (int i = 1; i <= n; ++ i) {
        for (int j = 0; j <= m; ++ j) {
            if (j < w[i]) c[i][j] = (f[n][j] + c[i][j]) % 10;
            else c[i][j] = (((c[i][j] + f[n][j]) % 10) - c[i][j - w[i]] + 10) % 10;
        }
    }
    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= m; ++ j) printf("%lld", (c[i][j] + 10) % 10);
        puts("");
    }
    return 0;
}