容斥做法：
首先n^2搞出f[i][j]第i个物品，j体积的方案数。
去除每个物品贡献：
设个g[i][j]表示当i不选，j体积方案数（注意不是此时的范围相对于全局，而不是1---i）
那么我们用到一些容斥的思想
g[i][j]=f[n][j]-g[i][j-w[i]]
因为g[i][j-w[i]]即可表示当i选时的方案数(都是相对于全局的)
而且注意枚举顺序，我们要用当前g[i]的状态更新之后个g[i]的状态，
而且在j<w[i]的情况下g[i][j]=f[n][j]
注意取模.....
1 #include<map>
2 #include<iostream>
3 #include<cstdio>
4 #include<cstring>
5 #include<algorithm>
6 #include<cmath>
7 #include<string>
8 #include<vector>
9 #define MAXN 4101
10 #define int long long
11 using namespace std;
12 int f[MAXN][MAXN];
13 int g[MAXN][MAXN];
14 int n=0,w[MAXN];
15 int sum=0;
16 signed main()
17 {
18 scanf("%lld%lld",&n,&sum);
19 for(int i=1;i<=n;++i)
20 {
21 scanf("%lld",&w[i]);
22 }
23 f[0][0]=1;
24 for(int i=1;i<=n;++i)
25 {
26 for(int j=sum;j>=0;--j)
27 {
28 f[i][j]=f[i-1][j];
29 }
30 for(int j=sum;j>=w[i];--j)
31 {
32 f[i][j]=(f[i][j]+f[i-1][j-w[i]]+10)%10;
33 }
34 }
35 for(int i=1;i<=n;++i)
36 {
37 for(int j=0;j<=w[i]-1;++j)
38 {
39 g[i][j]=(f[n][j]+10)%10;
40 }
41 for(int j=w[i];j<=sum;++j)
42 {
43 g[i][j]=(f[n][j]-g[i][j-w[i]]+10)%10;
44 }
45 }
46 for(int i=1;i<=n;++i)
47 {
48 for(int j=1;j<=sum;++j)
49 {
50 printf("%lld",(g[i][j]+10)%10);
51 }
52 printf("\n");
53 }
54 }
分治：
%%%%skyh，非常强的思路
我们按照分治的做法，其实每一次我们只是不选其中的一件物品，其余不变，
那么我们利用这个性质，只用除了自身以外的物品更新当前答案
让我们想起树的结构，把叶子节点当作询问，
只需要每次递归左右区间，查询叶子节点时，左右都已经更新答案
回溯时重新更新
1 #include<iostream>
2 #include<cstdio>
3 #define int short
4 using namespace std;
5 const int N=2010;
6 int n,m,w[N],dp[15][N];
7 inline void add(int &a,int b){
8 a+=b;
9 if(a>=10) a-=10;
10 }
11 void solve(int dep,int l,int r){
12 if(l==r){
13 for(int i=1;i<=m;++i) printf("%hd",dp[dep-1][i]);
14 puts("");
15 return ;
16 }
17 int mid=l+r>>1;
18 for(int i=0;i<=m;++i) dp[dep][i]=dp[dep-1][i];
19 for(int i=mid+1;i<=r;++i) for(int j=m;j>=w[i];--j) add(dp[dep][j],dp[dep][j-w[i]]);
20 solve(dep+1,l,mid);
21 for(int i=0;i<=m;++i) dp[dep][i]=dp[dep-1][i];
22 for(int i=l;i<=mid;++i) for(int j=m;j>=w[i];--j) add(dp[dep][j],dp[dep][j-w[i]]);
23 solve(dep+1,mid+1,r);
24 }
25 signed main(){
26 scanf("%hd%hd",&n,&m);
27 for(int i=1;i<=n;++i) scanf("%hd",&w[i]);
28 dp[0][0]=1; solve(1,1,n);
29 return 0;
30 }
%%%skyh