Solution

方法 $: D P, f (i, j)$ 使用前i个物品填满j的空间的方案数：
$F (i, j) = f (i - 1, j) + f (i - 1, j - w (i)), f (0, 0) = 1$
$c (i, j)$ 表示 $c o u n t (i, j),$ 分三种情况
$1, j > = w (i), c (i, j) = f (n, j) - c (i, j - w (i))$ 即用填满j的总方案数 $（ f (n, j) ）$ 减去使用了第 $i$ 个物品的方案数，其中使用第i个物品填满j的空间的方案数等于使用其余物品填满 $j - w (i)$ 的空间的方案数 $（ c (i, j - w (i)) ）$ 。
$3, 0 < j < w (i), c (i, j) = f (n, j)$ ，此时无论怎么填，都不会用到第 $i$ 个物品，答案所以等于总方案数。
$4, j = 0, c (i, j) = 1$

Code

#include<bits/stdc++.h>
using namespace std;
const int N=2001;
int n,m,i,j,w[N],f[N],t[N];
inline char gc(){
	static char buf[100000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd(){
	int x=0,fl=1;char ch=gc();
	for (;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;
	for (;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);
	return x*fl;
}
int main(){
	n=rd();m=rd();
	f[0]=1;
	for (i=0;i<n;i++){
		w[i]=rd();
		for (j=m;j>=w[i];j--) (f[j]+=f[j-w[i]])%=10;
	}
	for (i=0;i<n;i++,puts(""))
		for (t[0]=1,j=1;j<=m;j++) t[j]=(f[j]-(j>=w[i])*t[j-w[i]])%10,putchar((t[j]+10)%10|48);
}