[文章目录]
Description
ftiasch 有 N 个物品, 体积分别是 W1, W2, ..., WN。 由于她的疏忽, 第 i 个物品丢失了。 “要使用剩下的 N - 1 物品装满容积为 x 的背包，有几种方法呢？” -- 这是经典的问题了。她把答案记为 Count(i, x) ，想要得到所有1 <= i <= N, 1 <= x <= M的 Count(i, x) 表格。N(1≤N≤2000) 和 M(1≤M≤2000)
f[i]表示体积为i的方案数
考虑容斥：去掉i物品的方案数为f[m]-f[m-w[i]]+f[m-w[i]*2]......
ans直接递推一下就好了。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,w[2100],f[2100],num[2100];
int main()
{
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++)
{
memset(num,0,sizeof num);
for(int j=0;j<=m;j++)
{
num[j]=f[j];
if(j-w[i]>=0) num[j]=(num[j]-num[j-w[i]]+10)%10;
if(j!=0) printf("%d",num[j]);
}
puts("");
}
return 0;
}