最惨的事大概就是被讨厌的人吊打

懵逼的 题目

扯淡的 题解

首先我们先把所有都没少的背包方案求出来

然后考虑去掉一个数的影响, 如果f[x]直接减去f[x - w[i]]会因为x - w[i]可能由w[i]组成而GG

所以考虑归纳, 如果我们能求出来cnt[i][x - w[i]], 我们就可以直接放心减去这个cnt[i][x - w[i]](因为这个x - w[i]里肯定不会包含w[i]), 然后再考虑这个cnt[i]怎么求, 显然当x < w[i]时, f[x] = cnt[i][x], 然后递推就行了

据说这玩意叫多项式除单项式

沙茶的 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (2000 + 5)
#define MAXM (2000 + 5)
using namespace std;
int n, m, cnt[MAXN][MAXN], f[MAXN], w[MAXN];
int main()
{
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
    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;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= m; j++)
            cnt[i][j] = f[j];
        for (int j = w[i]; j <= m; j++)
            cnt[i][j] = ((cnt[i][j] - cnt[i][j - w[i]]) % 10 + 10) % 10;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            printf("%d", cnt[i][j]);
        puts("");
    }
    return 0;
}

By 联赛钦定爆零的 Cansult