Description：

有 $ N $ 个物品，每个物品有体积，设 $c[i][j]$ 为除去第 $i$ 个物品之外的 $n-1$ 个物品放 $j$ 的容积的方案数，求 $c[i][j]$ 。

$1\leqslant n,m\leqslant 20000$

Solution：

首先先求出 $f[j]$ ，表示可以用 $n$ 个物品放 $j$ 的容积的方案数，这个只要 $01$ 背包就可以了。

求 $c[i][j]$ 的时候分类讨论， $j<v[i]$ 时， $c[i][j]=f[j]$ ， $j\geqslant v[i]$ 时，应该从没有限制的方案数中减去包含第 $i$ 个的方案数，没有限制的就是 $f[j]$ ，包含第 $i$ 个就先强制选上第 $i$ 个，剩余的就变成用其他 $n-1$ 个物品填满 $j-v[i]$ 的体积，这个就是 $c[i][j-v[i]]$ ，所以就可以在 $O(NM)$ 的时间复杂度内计算出来了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 2010

int f[MAXN];

int v[MAXN];

int c[MAXN][MAXN];

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)scanf("%d",&v[i]);

	f[0] = 1;

	for(int i = 1;i <= n;++i)

		for(int j = m;j >= v[i];--j)

			f[j] = (f[j] + f[j - v[i]]) % 10;

	for(int i = 1;i <= n;++i)

	{

		for(int j = 0;j <= m;++j)

		{

			if(j < v[i])c[i][j] = f[j];

			else c[i][j] = (f[j] - c[i][j - v[i]] + 10) % 10;

		}

	}

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= m;++j)

		{

			putchar(c[i][j] + '0');

		}

		puts("");

	}

	return 0;

}