---
# System prepended metadata

title: MDCPP 模擬賽 題目 / 題解

---

# MDCPP 模擬賽 題目 / 題解

RANK : 

![](https://i.imgur.com/9cmbS1T.png)




## 1 Increasing Array

### Author : 91XB41
### Time Limit : 1000 ms
### Description 

:::spoiler 題敘(左側三角形點開)

---

給你一個陣列 $A$，你需要透過修改使得這個陣列呈非嚴格遞增，也就是後一個數字要大於等於前一個數字。

每次修改你可以任選一個 $i$，讓 $A_i = A_i + 1$ 。

求最少需要修改幾次才能完成。

---

:::

### Input Description


:::spoiler 輸入說明(左側三角形點開)

---

給你一個數字 $N$

代表接下來有長為$N$的陣列

接下來一行有$N$個數字$N_i$

$N \leq 10^6$

$A_i \leq 10^{18}$

---

:::


### Output Description

:::spoiler 輸出說明(左側三角形點開)

---

輸出最少修改次數

---

:::

### Sample 

:::spoiler 輸出說明(左側三角形點開)

---

input 1:
```

5
3 2 5 1 7

```

output 1:
```

5

```



---

:::



---

這題既然是第一題解法自然用最基礎的方式去想就好了
不過因為一些技術上的問題，很遺憾的只能讓你們拿到98分

好正式進入題解

這題因為要非嚴格遞增，所以基本上我們只要抓出不符合狀況(後面比前面小的)
然後把他加到跟前面一樣大(非嚴格)，就能在改變最少東西的情況下修正
就能夠得出需要花費的最少費用

如果覺得有點疑惑的話，建議還是多想一下吧

因為這題真的滿簡單的，所以我們還是直接上code吧

範例code
:::spoiler

```cpp=

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main () {
	int n , ans = 0;
	cin >> n;
	int a[n];
	for(int i = 0;i < n;i++){
		cin >> a[i]; 
	}
	for(int i = 1;i < n;i++){
		if(a[i] < a[i - 1]){ // 判斷是否有後面比前面小
			ans += a[i - 1] - a[i]; // 把他加到跟前面一樣大的花費
			a[i] = a[i - 1]; // 讓他跟前面一樣大
		}
	}
	cout << ans;
}

```

:::



## 2 大富翁

### Author : oolala
### Time Limit : 1000 ms
### Description 

:::spoiler 題敘(左側三角形點開)

---

有一位小朋友在玩大富翁，一共有 $N$ 個格子，有些格子已經被佔領，若停在該格上，則需要付過路費 $A_i$。

已知這位小朋友從第零格開始，擲了 $M$ 次骰子，每次前進擲中的結果 $B_i$，請問到終點時 (抵達 or 超過第 $N$ 格) 這位小朋友須付出多少錢 ?

---

:::

### Input Description


:::spoiler 輸入說明(左側三角形點開)

---

第一行輸入兩整數 $N, M$

第二行輸入 $N$ 個整數 $A_i$，代表每隔的過路費 ( 0 代表該格尚未被占領 )

第三行輸入 $M$ 個整數 $B_i$，代表每次擲中的結果

$M \leq N \leq 10000$

$A_i \leq 1000$, $1 \leq Bi \leq 6$

---

:::


### Output Description

:::spoiler 輸出說明(左側三角形點開)

---

輸出所需的過路費

---

:::

### Sample 

:::spoiler 輸出說明(左側三角形點開)

---

input 1:
```

6 3
3 2 1 3 2 1
3 1 4

```

output 1:
```

4

```

input 2:
```

14 6
0 0 0 359 0 0 0 473 0 867 487 0 0 0 
4 1 1 4 3 5 

```

output 2:
```

1226

```

---

:::





---


這題要怎麼解決呢 ? 模擬就好啦 ~
我們就設立一個變數 s = 0
每次加上走的步數，就會是目前走到的那個步數
當我們知道目前走到的那個步數，就可以知道當格需要花費多少的費用

只要把每格需要花費的費用加在一起，就可以成功得到最終費用了
順利拿到AC~~

範例code
:::spoiler

```cpp=

#include <bits/stdc++.h> 
#define int long long
using namespace std;
 

int arr[10050];

signed main(){
	
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>arr[i]; 
	
	
	int s = 0; // 起始點
	int cost = 0; // 總共的花費
	int plus; // 增加的步數
	for(int i=1;i<=m;i++){
		cin>>plus;
		s += plus; // 從起始點多走了plus步
		cost += arr[s]; // 加上當前那格的花費
		
	}
	cout<<cost<<endl; // 輸出總花費
	
	
}


```

:::




## 3 TC 與9x9立可帶

### Author : 91XB41
### Time Limit : 1000 ms
### Description 

:::spoiler 題敘(左側三角形點開)

---

TC 覺得9x9的39元立可帶實在太便宜、太好用了

因此他決定要把口袋裡所有錢通通拿來買39元立可帶

假設他每隔5分鐘就買一個立可帶

請你記錄他買立可帶的過程

---

:::

### Input Description


:::spoiler 輸入說明(左側三角形點開)

---

輸入為一正整數 $money$ ($39 \leq money \leq 1000$)

代表 TC 有多少錢

---

:::


### Output Description

:::spoiler 輸出說明(左側三角形點開)

---

每買一個立可帶就輸出兩行

格式如下方sample output

第一次買立可帶的時間為0:00

---

:::

### Sample 

:::spoiler 輸出說明(左側三角形點開)

---

input 1:
```

200

```

output 1:
```

0:00 TC bought white-out
money : 161
5:00 TC bought white-out
money : 122
10:00 TC bought white-out
money : 83
15:00 TC bought white-out
money : 44
20:00 TC bought white-out
money : 5

```



---

:::


---
其實不難看出本題是此次模擬賽的送分題，這題最主要就是測驗輸出文字的能力
但是在簡單的題目中其實藏有細節，有些人在輸出"money"時並沒有換行，導致WA
所以這題還是在提醒各位要注意輸出範例格式!!!

範例code

:::spoiler

```cpp=

#include<iostream>
using namespace std;

int main()
{
	int money;
	int minute = 0;
	
	cin >> money;
	while( money >=39)
	{
		money = money-39;
	
        cout << minute << ":00 Eric bought white-out" << endl;
		cout << "	money : " << money << endl;
		
		minute = minute+5;
	}	
	return 0;
}
    
```

:::




## 4 TC 的燙手山芋

### Author : reset007
### Time Limit : 1000 ms
### Description 

:::spoiler 題敘(左側三角形點開)

---

TC 有 $n-1$ 個好朋友
這天他突然得到一顆不知道哪來的燙手山芋
果不其然
懶惰的 TC 想把他丟給他的朋友們處理
然而他的朋友們也有相同的想法
結果
傳來傳去還是傳回了 TC 手上

假設一開始燙手山芋一定在 TC 手上
每個人都不會傳給自己
傳了 $k$ 次後
燙手山芋仍在 TC 手上的方法數為 $a_k$
請求出 ($n \times a_k$)除以48763的餘數是多少

為了讓 TC 不那麼可憐
保證 TC 一定有朋友

---

:::

### Input Description


:::spoiler 輸入說明(左側三角形點開)

---

輸入為兩整數 $n, k$
$n$ 代表總共有多少人在傳這顆燙手山芋 ( $2 \leq n \leq 1000$ )
$k$ 代表傳了多少次 ( $1 \leq k \leq 1000$ )

20%的測資滿足 $n,k \leq 5$
30%的測資滿足 $n \leq 100, k \leq 5$
49%無其他限制

(SPECIAL)1%( $n \leq 8763, k \leq 10^9$ )

---

:::

### Output Description

:::spoiler 輸出說明(左側三角形點開)

---

輸出為一個介於[0,48762]之間的整數
代表有多少種方法

---

:::

### Sample 

:::spoiler 輸出說明(左側三角形點開)

---

input 1:
```
2 3
```

output 1:
```
0
```

input 2:
```
5 4
```

output 2:
```
260
```
input 3:
```
87 87
```

output 3:
```
270
```

---

:::

### 文本內容
:::spoiler 在這
以下為提供語法班看的額外補充資料
可能會對這題有幫助
也可能不會

#### 遞迴與動態規劃(Recursive & DP)
這是一個「大事化小 小事化無」的解法
具體來說
我們會將較難的問題分解成小一點的 比較好理解或解決的問題
舉個栗子
「總共有n層階梯 你目前站在第0階
你每次可以選擇要走1階或是2階的階梯 請問你走到第n階有幾種方法數?」
思考一下就能發現
「走到第n階」只能透過「從第n-1階走一階上來」和「從第n-2階跨兩階上來」這兩個步驟來完成
若我們記F(n)為走到第n階的方法數
則F(n)=F(n-1)+F(n-2)
而且透過簡單計算可以知道F(1)=1, F(2)=2
這麼一來 我們知道它的規律
就能輕鬆求出所有答案了
他甚至只是個費氏數列
對了
階乘(!)也是遞迴喔
![](https://i.imgur.com/rjaTzYe.png)

小結:
![](https://i.imgur.com/TY0AXjx.png)

---

然而
遞迴是非常慢的
因為他會不斷的去call那些已經知道的東西
F(5)=F(4)+F(3)=( F(3)+F(2) )+F(3) (F3被叫了兩次)
所以會另外開設一個dp[]陣列
來存放我們已經知道的東西
我們可以寫說
```cpp=
dp[1]=1;
dp[2]=2;
for(int i=3;i<=n;i++){
    dp[i]=dp[i-1]+dp[i-2];
}
```
這樣只要跑n次就能得到答案了
這就是最基本的DP概念


#### 計數原理-乘法原理
例題
從你家出發有8種公車路線可以到台中車站
並且台中車站有8個車次的火車可以到達整修過還是很醜的彰化車站

$\Rightarrow$你有==8 $\times$ 8=64==種方式可以到彰化車站

像這種一次一次慢慢進行的行動
我們把每次小行動的方法數相乘
通常就能得到最終方法數

再來個栗子
今天有一隻青蛙和10片荷葉
青蛙一開始在其中一片荷葉上
他每次會往其他9片荷葉的其中一片跳
我們要求跳2次後回到一開始那片荷葉的跳法數

$\Rightarrow$第一跳有9種方法
但第二跳只能往原本的葉子跳

$\Rightarrow$總共有==9 $\times$ 1=9==個跳法

---

#### 快速冪
今天你想求$3^8$
你會慢慢的算$3\times 3\times 3\times 3\times 3\times 3\times 3\times 3$
還是把$3$平方平方再平方?
這就是快速冪的核心思想
與其一次一次自乘
不如用平方快速解決
那如果今天要求$487^{63}$呢?
我們拆成$487^{32} \times 487^{16} \times 487^8 \times 487^4 \times 487^2 \times 487$
其中較大的數都能透過小數平方得到
總共只要進行10次就能得到$487^{63}$囉(包括平方自乘與計算答案的相乘)
:::
### 題解
本題身為介於語法班和算法班之間的~~魔王~~過渡題
我分配了一些測資
是光靠基礎排列組合就能求出來的數學部分
以下解釋各配分的解法

:::spoiler 滿分解答code
先解釋一下這題的key point
>如果要在第$k$次傳給 TC
>那第$k-1$次就不能給 TC
>方法數 = 隨便亂傳-第$k-1$次在 TC 手上的方法
>而每次傳遞都有$n-1$種方法
>遞迴式$a_k=(n-1)^{(k-1)}-a_{k-1}$
>而且$a_1=0$(第1次不可能在TC手上)

到這裡你可以選擇開始解DP
但拿不到滿分
所以重點就是把這個遞迴式解成通式啦!
code:
```cpp=
#include<bits/stdc++.h>
using namespace std;
const int mod = 48763;

long long int fpow(int a, int b){
	long long int base = a, power = 1;
	while(b){
		if(b&1)power = (power*base)%mod;
		base = (base*base)%mod;
		b/=2;
	}
	return power%mod;
}

int solve(int n,int k){
	long long int answer;
	answer = fpow(n-1, k-1);
	if(k&1)answer--;
	else answer++;
	answer *= (n-1);
	return answer % 48763;
}

int main(){
    int n,k;
	cin>>n>>k;
	cout<<solve(n,k);
    return 0;
}
```
:::

:::spoiler 0~50分解
事實上小題1和2是幾乎一樣的
只是2的底數稍大
如果窮舉$n \leq 5, k \leq 5$的所有答案就能拿20分
如果能稍微把公式推廣到多一點人數的情形
就能再拿30
:::

:::spoiler 99分解
等到$k$變大後
單純套公式做遞迴鐵定會爆炸
所以就是我們dp的使用時機啦
dp陣列開到[1000][1000]是沒問題的喔
:::


## 5 地鐵
### Author : explosionnn
### Time Limit : 2000 ms
### Description

:::spoiler 提敘(右側三角形點開)

---

explosionnn喜歡在別人的minecraft伺服器蓋地鐵，而所有的地鐵路線呈網狀，代表某站與東西南北四站接連通。如今explosionnn從左上角的站點$(1, 1)$出發，欲前往右下角的站點$(n, m)$，一路上只往右或是下走。此外他有一顆終界珍珠，使用它能夠瞬間移動至下一站，而不花費任何時間，但是使用完珍珠即消滅。
現在給你移動到各站的時間，請求出從左上角移動到右下角最少需花費多少時間

---

:::

### Input Description


:::spoiler 輸入說明(右側三角形點開)

---

第一行有兩個整數 $N$ 和 $M$，代表這是此路網大小為$N*M$
接下來有$N$列，每一列有$M$個整數，第$i$列$j$行的整數$A_{i,j}$代表從左方或是上方的站點到達此站點須花費$A_{i,j}$的時間

---

:::

### Output Description

:::spoiler 輸出說明(右側三角形點開)

---

輸出從左上角移動到右下角最少需花費多少時間

---

:::

### Sample 

:::spoiler 輸出說明(右側三角形點開)

---

input 1:
```
3 3
1 7 3
50 8 8 
1 8 8
```

output 1:
```
18
```


input 2:
```
3 4
2 6 5 4
7 6 8 7
4 3 9 8
```

output 2:
```
24
```

---

:::

### 題解
想必大家剛接觸dp有寫過這種二維dp的經典題吧：
給定一個二維陣列，從左上走到右下，只能往右或是下走，問你怎麼走路上經過的點的和會最大或是最小？
而這題是加強版，多了一個終界珍珠，讓你可以忽視其中一點的值，那麼要怎麼做呢？

dp的陣列我們可以再開一個維度，最後一個維度的大小只有二，紀錄走到$A_{i, j}$的時候是不是已經用終界珍珠了，所以轉移式如下：
```cpp=
dp[i][j][0] = min(dp[i-1][j][0], dp[i][j-1][0]) + station[i][j];
dp[i][j][1] = min(min(dp[i-1][j][1], dp[i][j-1][1]) + station[i][j], min(dp[i-1][j][0], dp[i][j-1][0]));
```

$dp[i][j][0]$代表走到$A_{i, j}$的時候還沒使用過終界珍珠，這也代表走過來的路上也都沒有使用過。因此只能從$dp[i-1][j][0], dp[i][j-1][0]$這兩個第三維度同為$0$的值轉移過來，並且加上到達$A_{i, j}$的時間$station[i][j]$

$dp[i][j][1]$則代表走到$A_{i, j}$的時候已經使用過終界珍珠，可以分為兩個情況：
第一種情況為早就使用過了，所以從$dp[i-1][j][1]$或是$dp[i][j-1][1]$走到$A_{i, j}$的時候沒有珍珠可以用了，只能用走的。因此要從$dp[i-1][j][1], dp[i][j-1][1]$這兩個第三維度同為$1$的值轉移過來，並且加上到達$A_{i, j}$的時間$station[i][j]$

第二種情況為走到$A_{i, j}$的時候才用終界珍珠，因此在那之前是沒使用過的，轉移式為$min(dp[i-1][j][0], dp[i][j-1][0])$，最後不需要加上$station[i][j]$，因為是使用珍珠到達$station[i][j]$的


AC code
:::spoiler code

```cpp=
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define pii pair<int, int>
using namespace std;

const int MAXN = 2e3+5;
int INF = 1e18;
int station[MAXN][MAXN], dp[MAXN][MAXN][2];
int n, m;

signed main(){
	cin >> n >> m;
	for(int i = 0; i <= n; i++){
        for(int j = 0; j <= m; j++){
            dp[i][j][0] = dp[i][j][1] = INF;
        }
	}

	for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> station[i][j];
        }
	}

	for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(i == 1 && j == 1){
                dp[1][1][0] = dp[1][1][1] = station[i][j];
                continue;
            }
            dp[i][j][0] = min(dp[i-1][j][0], dp[i][j-1][0]) + station[i][j];
            dp[i][j][1] = min(min(dp[i-1][j][1], dp[i][j-1][1]) + station[i][j], min(dp[i-1][j][0], dp[i][j-1][0]));
        }
	}

	cout << dp[n][m][1] << "\n";

}

```

:::


## 6. TC 出遊去 

### Author : 極速車神大佬
### Time Limit : 4000 ms
### Description 
    
暑假了 ! 最近風和日麗，而 TC 打算帶他的眾多ㄌㄌ出去玩。
這個國家有 $N$ 個村莊，而由 $M$ 個道路連接村莊 $u$ 和 村莊 $v$，每個道路有一個長度 $W_i$。
他們打算每個村莊都要前往，但是 TC 為了照顧他的ㄌㄌ，所以他要盡量讓每次ㄌㄌ走的路不要太長。換句話說，他要選擇幾條道路，讓選擇的道路的最大值最小，並且能夠走完各個村莊。
註：TC 可以從任意一點開始，且道路是雙向的。

### Input Description

輸入有多筆測資。
第一行有個整數 $T$，代表測資個數
接下來一行有兩個整數 $N$ 和 $M$，代表有幾個村莊及道路。
接下來有 $M$ 行，每行有三個數字，
分別是 $u_i$、$v_i$、$w_i$，代表連接 $u_i$ 到 $v_i$ 的道路長度是 $w_i$

$1 \leq T \leq 100$
$2 \leq N \leq 10^5$
$1 \leq M \leq 10^6$
$1 \leq u_i, w_i \leq N$
$1 \leq w_i \leq 10^5$

$\ \sum_{i=1}^{T} N_T \leq 10^5$

部份給分 : 

30 % 給的圖是由 $N$ 個村莊，$N-1$ 個邊連接，並且保證能夠互相到達
30 % $w_i \leq 10$
40 % 無其他限制

### Output Description

請輸出道路最大值最小，若無論如何都無法到達，請輸出 impossible

### Sample 
```
// Sample input 1
1
4 4
1 2 1
2 3 2
1 3 1
1 4 1
// Sample output 1
1
// Sample input 2
2
4 5
1 2 1
2 3 3
1 3 2
2 4 4
3 4 3
6 5
1 2 2
2 3 5
4 6 2
5 6 3
1 3 4
// Sample output 2
3
impossible
// Sample input 3
1
2 1
1 2 10
// Sample output 3
10
```

這題究竟要怎麼完成呢 ?

對於 第一個 subtask:
我們可以發現為了要走到全部的點，每條邊一定要走到，所以將全部路徑長取 $max$ 即可
對於 第二個 subtask:
我們可以枚舉上限，從 1 ~ 10，依據上限來判斷可不可以走。
對於全部:
透過題目敘述可以發現，題目要你求道路長度的上限最小值。
而這又是一個外掛二分搜的模型：最大值最小。
我們知道如果上限越大的話，就越容易到達，這就構成了二分搜單調性
那要怎麼完成確認函數呢 ? 很簡單，我們就 DFS / BFS 一次就好，
而如果超過上限的邊就不去走他。
複雜度：$O((N+M)*logC)$
$O(N+M)$ 來自 DFS / BFS
$O(logC)$ 來自外掛二分搜
```cpp=
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define mset(a,b) memset(a,b,sizeof(a))
using namespace std;
const int maxn = 1e5 + 5 ;
vector<pii>g[maxn];
int vis[maxn],cnt,n,m;
void dfs(int x,int p,int c) {
	if(vis[x]++) return ;
	cnt++;
	for(auto [v,e]:g[x]) {
		if(v==p or e>c) continue;
		dfs(v,x,c);
	}
}
bool check(int c) {
	cnt=0;
	mset(vis,0);
	dfs(1,-1,c);
	if(cnt==n) return true;
	else return false;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--) {
           cin>>n>>m;
        for(int i=1;i<=n;i++) g[i].clear();
	    while(m--) {
		    int u,v,w;
		    cin>>u>>v>>w;
		    g[u].pb({v,w});
		    g[v].pb({u,w});
	    }
	    int l=1,r=1e4,best=-1;
	    while(l<=r) {
            int mid=(l+r)>>1;
		    if(check(mid)) best=mid,r=mid-1;
		    else l=mid+1;
	    }
	    if(~best) cout<<best<<endl;
	    else cout<<"impossible\n";
    }
}
```

而其實這題有另一個更好的方法，就是利用最小生成樹 (MST) !
這個算是比較進階的內容，有興趣的同學可以看[這裡](https://oi-wiki.org/graph/mst/#kruskal)
複雜度：$O(M*logM)$
這裡附上程式碼：
```cpp=
#include <bits/stdc++.h>
#define pb push_back
#define tup tuple<int,int,int>
using namespace std;
const int maxn = 1e5 + 5 ;
int pa[maxn],mx,cnt;
int findset(int x) {
	return x==pa[x]?x:pa[x]=findset(pa[x]);
}
vector<tup>edge;
void uni(int u,int v,int w) {
	u=findset(u),v=findset(v);
	if(u==v) return ;
	pa[u]=v;
	mx=w;
	cnt++;
}
bool cmp(tup t1,tup t2) {
	return get<2>(t1)<get<2>(t2); // tuple 用法
}
signed main()
{
	ios::sync_with_stdio(0);
        cin.tie(0);
	int t,n,m;
        cin>>t;
        while(t--) {
	    cin>>n>>m;
	    for(int i=1;i<=n;i++) pa[i]=i;
            edge.clear();
	    while(m--) {
		    int u,v,w;
		    cin>>u>>v>>w;
                   edge.pb({u,v,w});
	    }
	    sort(edge.begin(),edge.end(),cmp);
	    for(auto [u,v,w]:edge) {
		    uni(u,v,w);
	    }
	    if(cnt!=n-1) cout<<"impossible\n";
	    else cout<<mx<<endl;
    }
}

```

## 7 Tim Chen與黑市的白毛ㄌㄌ交易

### Author : YouZhe
### Time Limit : 600 ms
### Description 

:::spoiler 提敘(右側三角形點開)

---

眾所皆知Tim Chen是個狂熱的ㄌㄌ愛好者，最近他從黑市中找到了一個攤販，願意以吸引人的價格賣給他最上等的白毛ㄌㄌ

這個攤販花了不少心血才弄到一隻難能一見的白毛ㄌㄌ，因此他對於他的訂價絲毫不肯退讓

並且為了讓他在黑市的生意不要曝光，攤販不願意找任何錢，畢竟錢上是有編號的，找錢相當於讓自己的資訊流出

正好Tim Chen又是一個寧願不吃午餐來省錢的台南血脈客家人(或者他只是想要存錢去吃女僕咖啡廳)。因此他不可能做出給更多錢的舉動

也就是說他們之間的交易**只可能在剛好等於定價時發生，且只能付剛好的錢(不找錢)**

今天正是Tim Chen要買下白毛ㄌㄌ的日子，但黑市攤販跟他說當他來到黑市後才願意釋出價格$C$

因此他無法準備確切數目的紙鈔，最後他在錢包裡**準備了$N$種面額的紙鈔各一張**

但是在路上時，或許是因為滿腦都是白毛ㄌㄌ，所以**有$M$張鈔票從他的錢包掉了出去**

現在**給出$Q$次詢問，每次詢問給出$M$個數字**

代表Tim Chen**丟掉的鈔票面額**。

試問每次詢問中，Tim Chen有**幾種方法**可以湊到購買白毛ㄌㄌ的價格

若沒有任何湊到白毛ㄌㄌ價格的方法，請用力嘲笑他:"Ha! What a poor guy!"

(答案請對10^9+7取模)

---

:::

### Input Description


:::spoiler 輸入說明(右側三角形點開)

---

第一行有兩個整數$N$、$C$，代表攜帶的紙鈔數量、要賣出的價格

第二行，有$N$個數字$a_i$代表紙鈔的面額。

接下來有一個整數$Q$詢問的次數

接下來有$Q$組數字:

第一行有一個整數$M$代表遺失的紙鈔數量

第二行，有$M$個數字$b_i$代表遺失紙鈔的面額。

$1 \leq N \leq 2000$

$1 \leq C \leq 2000$

$1 \leq Q \leq 2000$

$1 \leq M \leq 10$

$1 \leq a_i, b_i \leq 2000$

b集合在a集合之中



部份給分

50%$1 \leq N, C, Q, a_i ,b_i  \leq 100$

50% 原測資

---

:::

### Output Description

:::spoiler 輸出說明(右側三角形點開)

---

請輸出湊到白毛ㄌㄌ價格的方法數，若為0，請輸出Ha! What a poor guy!

---

:::

### Sample 

:::spoiler 輸出說明(右側三角形點開)

---

input 1:
```
5 8
1 4 3 6 8
2
1
6
3
6 8 1
```

output 1:
```
2
Ha! What a poor guy!
```

---

:::

### 題解

這題呢我預估解出來的人也是在3個以內，不過因為其他題目太邪惡了，所以她就被排到了第6題

至於要怎麼解這題呢?
如果還記得背包DP的最後一堂課，那就會發現這題長的就一臉找錢問題對吧。
只不過要把它從無限背包的架構，改成01背包的架構
的確，這題就是那題找錢問題的延伸。不過我猜大多數人根本沒聽懂就是了。

首先這一看，先套進找錢問題的模板就是我們的第一步了

接下來，因為我們可以知道的是，它會有Q次查詢改變原本的物品
所以這裡可以直接看出第一種作法
O(QNC)的做法，我們只要改變Q次物品，並且每次都對它做一次背包DP
每次背包DP的複雜度是O(NC)，乘在一起就變成O(QNC)了，這也是前50%的拿法

阿因為不是AC code，所以我就不放範例code了

現在知道了O(QNC)，很顯然這在完全測資裡是會爆掉的
所以我們希望能在每次修改之後，不需要都多做一次背包DP
那麼就先觀察掉一種面額的鈔票會導致甚麼結果
很顯然，在背包DP裡，就是透過這種面額加到的方法數會失效嘛
```cpp=
for(int i=1;i<=n;i++)
    for(int j = c;j>=w[i];j--){
        dp[j] = dp[j]+dp[j-w[i]];
    }
```

那麼我們就反過來做，把他所得到的結果反過來扣掉
```cpp=
    for(int j=lost;j<=c;j++) //lost代表掉的錢面額
        ndp[j] = ndp[j]-ndp[j-lost];
    }
```
至於為甚麼要從小到大順推過去，而不是按照01背包那樣，由大到小逆堆呢
因為我們如果不先把小容量的背包扣掉的話，大容量的背包就會扣掉使用lost這個面額達成的方法數，變成扣了兩次

舉個例
有 1 2 3 4 面額 要湊到價格6
-|1|2|3|4|5|6
-|-|-|-|-|-|-
for i=1|1|0|0|0|0|0
for i=2|1|1|1|0|0|0
for i=3|1|1|2|1|1|1
for i=4|1|1|2|2|2|2

現在扣掉3這個面額

如果逆著做
-|1|2|3|4|5|6
-|-|-|-|-|-|-
原本|1|1|2|2|2|2
後來|1|1|1|1|1|0

因為6先扣掉了3的2種方法，所以掛了，本來還有2+4這種，算出來卻變0種
3的兩種方法包刮[1+2],[3]，如果6先扣它，就相當於扣了一個0+3+3的情況
但這顯然是不成立的，所以我們要正著做它

變成這樣
-|1|2|3|4|5|6
-|-|-|-|-|-|-
原本|1|1|2|2|2|2
後來|1|1|1|1|1|1

答案就會正確是1

以下附上範例code
:::spoiler code

```cpp=
#include <bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;
const int MAXN = 3000+50;
int dp[MAXN];
int w[MAXN];

signed main(){

int n,c;
cin>>n>>c;
for(int i=1;i<=n;i++){
    cin>>w[i];
}
    
dp[0] = 1;
for(int i=1;i<=n;i++)
    for(int j = c;j>=w[i];j--){
        dp[j] = (dp[j]+dp[j-w[i]])%mod;
    }
// 01背包架構的找錢
// O(NC)
    
int q;
cin>>q;
while(q--){

    int ndp[MAXN]; //new dp
    memcpy(ndp,dp,sizeof(dp));//O(NQ)
    //這個memcpy()代表把dp陣列複製給ndp陣列
    //你們也可以用for迴圈來做

    int m;
    cin>>m;
    int lost;
    for(int i=1;i<=m;i++){
        cin>>lost;
        for(int j=lost;j<=c;j++) //  順推 這樣才不會扣到已經用了lost來湊出的方法數，變成扣了兩次
            ndp[j] = (ndp[j]-ndp[j-lost]+mod)%mod; //前面即取過模，只取一次
    } //O(QMC)
    if(ndp[c]==0)
    cout<<"Ha! What a poor guy!"<<endl;
    else
    cout<<ndp[c]<<endl;
}


}

```

:::
