Table of Contents

1. 題目描述：
2. 題目簡化：
3. 解法一：樸素01背包 80pts
4. 解法二：補集輔助數組 100pts
5. 關于這篇題解：

題目描述：

## 題目描述

ftiasch 有 \(n\) 個物品, 體積分別是 \(w_1,w_2,\dots,w_n\)。由于她的疏忽，第 \(i\) 個物品丟失了。

“要使用剩下的 \(n-1\) 物品裝滿容積為 \(x\) 的背包，有幾種方法呢？”——這是經典的問題了。

她把答案記為 \(\text{cnt}(i,x)\) ，想要得到所有\(i \in [1,n]\), \(x \in [1,m]\) 的 \(\text{cnt}(i,x)\) 表格。

!

## 輸入格式

第一行兩個整數 \(n,m\)，表示物品的數量和最大的容積。
第二行 \(n\) 個整數 \(w_1,w_2,\dots,w_n\)，表示每個物品的體積。

## 輸出格式

輸出一個 \(n \times m\) 的矩陣，表示 \(\text{cnt}(i,x)\) 的**末位數字**。

## 輸入輸出樣例 #1

### 輸入 #1

```
3 2
1 1 2
```

### 輸出 #1

```
11
11
21
```

## 說明/提示

【數據范圍】
對于 \(100\%\) 的數據，\(1\le n,m \le 2000\)，且 \(1\le w_i\le 2000\)。

【樣例解釋】
如果物品 3 丟失的話，只有一種方法裝滿容量是 2 的背包，即選擇物品 1 和物品 2。

—

\(\text{upd 2023.8.11}\)：新增加五組 Hack 數據。

題目簡化：

給定n個物品和容量為m的背包，此時我們令物品 \(i \in [1,n]\) 不可選，令背包容量 \(v \in m\) 逐漸增加，輸出去除每種物品后對于正好填滿每種背包大小的方案數的個位；

解法一：樸素01背包 80pts

這道題最樸素的做法是 \(O(n^2 \times m)\) 的，我們每次更改不可用的物品 \(i\) 時，都重新進行一次dp數組計算，而每次dp的計算都是 \(O(n \times m)\) 的，所以總體時間復雜度 \(O(n^2 \times m)\) ；
沒什么好解釋的，這里不給代碼了；

解法二：補集輔助數組 100pts

我們注意到： \(O(n^2 \times m)\) 的時間復雜度明顯不可接受，那么唯一可能的復雜度是 \(O(n \times m)\) 的，也就是說，我們對于去除一個元素的這個操作，需要 \(O(1)\) 完成；
因此我們需要設計出如何通過dp數組直接求出去除一個物品的答案，這里我們根據補集的思想進行設計：

不難發現： 總方案數 = 選i的方案數 + 不選i的方案數 ；
我們最終要求出的就是不選i的方案數，所以我們要做的就是以 \(O(1)\) 的復雜度求出不選i的方案數；

我自己做這道題的時候做了2小時，想出來了解法：
我們維護一個數組 \(f_v\) ，定義為容量為v時不選i的方案數，那么 \(f\) 怎么計算呢；
顯然有 \(f_0 = 1\) ；
隨后，當 \(j<w_i\) 時，代表此時的背包容量不足以放下物品i，所以此時的 \(f_j = dp_j\) ;
當 \(j>=w_i\) 時，此時的 \(f_v\) 應該是多少呢；
由：“總方案數 = 選i的方案數 + 不選i的方案數”，可得：不選i的方案數 = 總方案數 - 選i的方案數
即為 \(f_j = dp_j - f_{j-w_i}\) ;

這里非常疑惑的一個點是：選i的方案數為什么是 \(f_{j-w_i}\) ;
補充一個引理：背包問題的最優解與放入物品的順序無關（這是顯然的，無后效性的體現）
我們可以這樣理解：對于一個選i的方案而言，我們可以認為i是最后一個物品，先不選i填充容量為 \(j-w_i\) 的背包，隨后使用i填充完整；
由于最后一個一定選i，所以方案數為：不選i填充容量為 \(j-w_i\) 的背包的方案數 ，即為 \(f_{j-w_i}\) ；

總結一下： \(f_j = dp_j - f_{j-w_i}\) (當 \(j>=w_i\) 時)， \(f_j = dp_j\) (當 \(j<w_i\) 時);

經過我們的一番推理，最終得出了不選i的方案數，這就是我們想要的答案，根據要求中途取模輸出即可；

關于這篇題解：

我自己做這道題時感覺非常非常崩潰，仿佛自己沒學過dp，不過好歹是AC了；
僅以此文，記錄一下我奮斗的8月22日；