题意描述

$\text{ftiasch}$ 有 $n$ 个物品, 体积分别是 $w_1,w_2,\dots,w_n$。

由于她的疏忽，第 $i$ 个物品丢失了。

“要使用剩下的 $n-1$ 物品装满容积为 $x$ 的背包，有几种方法呢？”——这是经典的问题了。

她把答案记为 $cnt(i,x)$ ，想要得到所有$i \in [1,n]$ , $x \in [1,m]$的 $cnt(i,x)$表格。

然而她不会做，所以这个问题扔给了你

输入格式

第一行两个整数 $n,m$，表示物品的数量和最大的容积。
第二行 $n$ 个整数 $w_1,w_2,\dots,w_n$ ，表示每个物品的体积。

输出格式

输出一个 $n \times m$ 的矩阵，表示 $cnt(i,x)$ 的末位数字

即$cnt(i , x)$对$10$取模的结果

Input & Output ‘s examples

Input ‘s eg

3 2
1 1 2

Output ‘s eg

11
11
21

数据范围和约定

对于 $100\%$ 的数据，$1\leq n,m \leq 2000$

分析

$01$背包计数 + 简单容斥。

先考虑一下暴力怎么做：可以依次枚举丢失的物品跑$01$背包，时间复杂度为$O(n^2m)$，跑不过本题。

考虑一下刚刚暴力的瓶颈在哪，显然，瓶颈在于枚举丢失的物品。则我们考虑不采用枚举来算出结果。然而这并不好做。

正难则补，考虑容斥。设$f[i][j][0]$表示前$i$个物品，不算消失的物品，组成价值为$j$的方案数。则：

$f[i][j][0] = f[i][j][0] + f[i - 1][j - v[i]][0]$

设$f[i][j][1]$表示前$i$个物品，算上消失的物品，组成价值为$j$的方案数。显然，这可以由$f[i][j][0]$减去需要加上v[i]才能组成大小为j的方案数得来。即：

$f[i][j][1] = f[i][j][0] - f[i - 1][j - v[i]][1]$

最后别忘了取模，输出即可。

顺便提一个小细节，如果你像作者一样采用了滚动数组的写法，请一边处理一边输出。

这是因为滚动数组压掉了子状态，而本题又要求输出所有状态所致。

剩下的见代码注释。

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define ll long long
#define pb push_back
#define MP make_pair
#define ull unsigned long long
#define PII pair<int , int>
#define PIL pair<int , long long>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

using namespace std;

const int N = 10001;
const int M = 100001;
const int HA = 10;
const int INF = 2147483647;
const long long INFL = 9223372036854775807;

int f[M][2] , v[M]; 

//f[j][0] 不考虑丢失物品，组成体积为j的背包的方案数
//f[j][1] 考虑丢失物品，组成体积为j的背包的方案数

int main() {
    #ifdef LOCAL
        freopen("try.in" , "r" , stdin);
        freopen("try1.out" , "w" , stdout);
    #endif
    int n , m; scanf("%d%d" , &n , &m);
    rep(i , 1 , n){
        scanf("%d" , &v[i]);
    }
    f[0][0] = 1; f[0][1] = 1;
    rep(i , 1 , n){     //dp求01背包方案数
        per(j , m , v[i]){
            f[j][0] += f[j - v[i]][0];
            f[j][0] %= HA;
        }
    }
    rep(i , 1 , n){     
        rep(j , 1 , m){
            if(j - v[i] >= 0){  //避免访问负下标导致RE  
                //容斥，减去需要加上v[i]才能组成j的方案数
                f[j][1] = f[j][0] - f[j - v[i]][1];
                f[j][1] %= HA;
            }
            else{
                f[j][1] = f[j][0] % HA;
            }
            printf("%d" , f[j][1]); //边处理变输出
        }
        puts("");
    }

    return 0;
}