( ext{Description})
( ext{Solution})
真的好妙。
先 (mathcal O(n imes m)) 做一个 (01) 背包，算出所有物品放入容量为 (j) 的背包为 (f[j])。
设 (g[i][j]) 为答案数组。直接考虑我们平时是怎么添加一个物品进入 (01) 背包：
[f[j]+=f[j-w[i]]
]
这里也是一样的，我们可以将这个过程倒过来！我们已经知道 (f[j])，只要计算出容量为 (j-w_i) 的不包含 (i) 的方案数（这个方案数也是我们在计算 (f) 所认为的 (i) 能向 (j) 贡献的新方案）。
递推式：
[g[i][j]=f[j]-g[i][j-w[i]]
]
( ext{New Idea!})
发现这个做法可以拓展到多重背包，但是因为博主太鶸复杂度只能做到 (mathcal O(n imes m imes k))。
我们先预处理 (f) 算出正常多重背包方案数。对于一个有 (k_i) 件的物品 (i)，令 (g[i][j]) 为最多有 (k_i-1) 件物品 (i)，容量为 (j) 的方案数。
也是和之前一样地考虑如何加入一个物品到多重背包，显然我们在第 (i) 件的关于个数的循环的最后一个循环是最多有 (k_i-1) 件物品 (i)，体积为 (j-w_i) 的方案数再加上一个物品 (i) 就能凑到 (j)，递推式同上。
得到 (g) 数组，我们同样可以令 (h[i][j]) 为最多有 (k_i-2) 件物品 (i)，容量为 (j) 的方案数。
(...)
显然这个要进行 (k) 层。
自己 ( ext{YY}) 的应该是对的叭。
( ext{Code})
#include <cstdio>
#define rep(i,_l,_r) for(register signed i=(_l),_end=(_r);i<=_end;++i)
#define fep(i,_l,_r) for(register signed i=(_l),_end=(_r);i>=_end;--i)
#define erep(i,u) for(signed i=head[u],v=to[i];i;i=nxt[i],v=to[i])
#define efep(i,u) for(signed i=Head[u],v=to[i];i;i=nxt[i],v=to[i])
#define print(x,y) write(x),putchar(y)
template <class T> inline T read(const T sample) {
T x=0; int f=1; char s;
while((s=getchar())>'9'||s<'0') if(s=='-') f=-1;
while(s>='0'&&s<='9') x=(x<<1)+(x<<3)+(s^48),s=getchar();
return x*f;
}
template <class T> inline void write(const T x) {
if(x<0) return (void) (putchar('-'),write(-x));
if(x>9) write(x/10);
putchar(x%10^48);
}
template <class T> inline T Max(const T x,const T y) {if(x>y) return x; return y;}
template <class T> inline T Min(const T x,const T y) {if(x<y) return x; return y;}
template <class T> inline T fab(const T x) {return x>0?x:-x;}
template <class T> inline T gcd(const T x,const T y) {return y?gcd(y,x%y):x;}
template <class T> inline T lcm(const T x,const T y) {return x/gcd(x,y)*y;}
template <class T> inline T Swap(T &x,T &y) {x^=y^=x^=y;}
const int maxn=2005;
int n,m,w[maxn],f[maxn],g[maxn];
int main() {
n=read(9),m=read(9);
rep(i,1,n) w[i]=read(9);
f[0]=1;
rep(i,1,n) fep(j,m,w[i]) f[j]=(f[j]+f[j-w[i]])%10;
g[0]=1;
rep(i,1,n) {
rep(j,1,m) {
if(j>=w[i]) g[j]=(f[j]-g[j-w[i]]+10)%10;
else g[j]=f[j];
if(j==m) print(g[j],'
');
else write(g[j]);
}
}
return 0;
}