---
tags: solution
---
*[返回教材目錄](https://hackmd.io/@PuSaff/ryqPRzENq)*
<style>
.blackout {
color: #191919;
background-color: #191919;
}
.blackout:hover {
color: white;
}
</style>
# a232 骰子組合
> 給定三個數字 $N, M, F$，請求出執行一個範圍$1\sim F$ 的亂數生成器，在執行 $N$ 次後，將所有數字加起來等於 $M$ 的方法數。
>
> ***Tags:** 暴力(brute-force), 動態規劃(DP)*
:::spoiler <b>注: 滑鼠移動到<span class=blackout> 黑條 </span>上自動反白，點開</b>
會顯示Subtask詳解，想自己解的自行注意
:::
----
## Subtask 1.
如果我已經知道骰兩顆六面骰骰到1~12點分別有幾種，那麼我能怎麼算出骰三顆骰子骰到一點、兩點、三點...的方法數呢?
:::spoiler **關鍵字: <span class=blackout> 暴力遞迴 </span>**
如果骰兩顆骰子要得到7點，那就是
* 第一顆1點，第二顆6點
* 第一顆2點，第二顆5點
* 第一顆3點，第二顆4點
* ...
* 第一顆6點，第二顆1點
<br>
如果要三顆骰7點呢? 跟上面很相似
* 前兩顆1點，第二顆6點
* 前兩顆2點，第二顆5點
* 前兩顆3點，第二顆4點
* ...
* 前兩顆6點，第二顆1點
由此可知，想得知`n`顆骰子骰到`m`點的情形，可以由`n-1`顆骰子的情形推得。以六面骰為例的話，即前`n-1`顆骰到`m-6, m-5, m-4, m-3, m-2`或`m-1`，第`n`顆再骰到對應的點數。
```cpp=
#include <iostream>
using namespace std;
const int MOD = 998244353;
long long recur(int n, int m, int f) {
if (n == 1) //一顆骰的點數為1~F
return (n > 0) && (n <= f);
long long sum = 0;
for (int i=1; i<=f; ++i) {
sum += recur(n-1, m-i, f);
sum %= MOD;
}
return sum % MOD;
}
signed main() {
long long n, m, f;
cin >> n >> m >> f;
cout << recur(n, m, f) << '\n';
return 0;
}
```
時間複雜度: $O(N^F)$
:::
## Subtask 2.
$N, M$的範圍變大了，用`Subtask 1`的解的話會`TLE`。想一想在`Subtask 1`的寫法裡面，有沒有多餘的計算?
:::spoiler **關鍵字: <span class=blackout> 動態規劃 </span>**
以 $N, M, F = 5, 10, 3$ 為例，呼叫`Subtask 1`中我們的遞迴函式，大約會長這樣:
```graphviz
digraph G {
R[label="f(5, 10, 3)"]
A0[label="f(4, 9, 3)"]
A1[label="f(4, 8, 3)"]
A2[label="f(4, 7, 3)"]
B0[label="f(3, 8, 3)"]
B1[label="f(3, 7, 3)"]
B2[label="f(3, 6, 3)"]
B3[label="f(3, 5, 3)"]
B4[label="f(3, 4, 3)"]
R -> A0, A1, A2
A0 -> B0, B1, B2
A1 -> B1, B2, B3
A2 -> B2, B3, B4
}
```
從上面的圖可以發現，我們呼叫了許多參數完全相同的函式。這就像是，在數學考試中剛剛才花很多時間解完一題，下一題問你一模一樣的題目，你還再重算一次的意思是一樣的。
聰明的作法，是將答案記起來，之後如果有問到一樣的東西就不用重算了。
```cpp=
#include <iostream>
#include <algorithm>
using namespace std;
const int MOD = 998244353;
long long dp[105][105];
long long DP(int n, int m, int f) {
if (0 >= m) return 0;
if (n == 1) return (1 <= m) && (m <= f);
if (dp[n][m] != 0) return dp[n][m];
for (int i=1; i<=f; i++)
dp[n][m] = (dp[n][m] + DP(n-1, m-i, f)) % MOD;
return dp[n][m];
}
```
以上是遞迴(`Top-down`)的做法，但比起用迴圈(`Bottom-up`)慢很多。將`Top-down`改成`Bottom-up`的做法，就是利用特殊的計算順序，讓我們在算到`f(a, b, c)`的時候，所需用到的`f(a-1, b-1, c), f(a-1, b-2, c)...`都已經被我們算好了。
<table>
<tr>
<th></th>
<th>Top-down作法</th>
<th>Bottom-up作法</th>
</tr>
<tr>
<th>優勢</th>
<td><b>比較好寫</b>，只要推出關係式，基本上程式就出來了</td>
<td>不必一值呼叫自己，而<b>節省了執行時間</b></td>
</tr>
</table>
```cpp=
#include <iostream>
#include <algorithm>
using namespace std;
const int MOD = 998244353;
long long dp[105][105];
long long gv(int idx, int r) { //避免戳到負的位置
if (idx <= 0) return 0;
return dp[r][idx];
}
long long DP(int n, int m, int f) {
for (int i=0; i<=n; ++i)
fill(dp[i], dp[i]+m+1, 0);
fill(dp[1]+1, dp[1]+1+f, 1);
//先算丟一顆骰，再算丟兩顆，再算丟三顆...
for (int i=2; i<=n; ++i) {
for (int j=i; j<=m; ++j) {
for (int k=1; k<=f; ++k) {
dp[i][j] = (dp[i][j] + gv(j-k, i-1)) % MOD;
}
}
}
return dp[n][m];
}
```
時間複雜度: $O(NMF)$
:::
## Subtask 3.
$N, M$ 的範圍變更大了。`Subtask 2`的時間複雜度還是可以過，但是本題的記憶體限制在`64MB`，不夠用。想一想有沒有哪些資訊，是在程式執行的過程中就能被拋棄的，而不必一直記錄到最後?
:::spoiler **關鍵字: <span class=blackout> 滾動式DP </span>**
我們再看看`Subtask 2`中寫的DP。將他的轉移式(從上一個狀態推得下一個狀態的數學式)寫出來，大概是這樣的:
$$
dp[i][j] = \sum_{k=1}^{k\leq F}{dp[i-1][j-k]}
$$
有沒有發現甚麼? 想要得到骰了`n`顆骰子的情形，我們需要，而且**只需要**，知道骰了`n-1`顆骰子的情形即可，`n-2, n-3, n-4...`顆骰的情形已經不重要了。
照這個邏輯走下去，我們可以將之前的`DP`改一改: 在即將計算`n=3`顆骰時，將之前算的`n=1`顆骰時所紀錄的答案丟掉；在即將計算`n=4`顆骰時，將`n=2`顆骰的答案丟掉...
```cpp=
//計算n顆骰時，只會用到n-1顆骰時的情形。
//因此只需要兩個陣列，分別是:
//新計算的，n顆骰時的情形，存到dp[1]裡面
//曾算過的，n-1顆骰時的情形，存在dp[0]裡面
long long dp[2][3005];
long long rollingDP(int n, int m, int f) {
fill(dp[0], dp[0]+3005, 0);
fill(dp[0]+1, dp[0]+1+f, 1);
for (int i=1; i<n; ++i) {
for (int j=i+1; j<=m; ++j) {
for (int k=1; k<=f; ++k) {
dp[1][j] = (dp[1][j] + gv(j-k)) % MOD;
}
}
//即將計算n+1顆骰時的情形
//將dp[1]裡面的東西複製到dp[0]裡面
//(這裡用swap，但結果一樣)
//再將dp[1]重製
swap(dp[0], dp[1]);
fill(dp[1], dp[1]+3005, 0);
}
return dp[0][m];
}
```
原空間複雜度: $O(NM)$
新空間複雜度: $O(N)$
:::
## Subtask 4.
$F$ 的範圍變大了，`Subtask 3`的解法的不足以應付了，會`TLE`。像`Subtask 1 → 2`時那樣，檢查看看有沒有多餘的計算吧。
:::spoiler **關鍵字: <span class=blackout> 前綴和/滑窗 </span>**
我們再回到轉移式觀察看看:
$$
dp[i][j] = \sum_{k=1}^{k\leq F}{dp[i-1][j-k]}
$$
... ...看不出甚麼東西?
不如拿一些數字丟進去，看看計算的過程是怎麼樣的。
```
N, M, F = 6, 17, 4
...
dp[3][7] = dp[2][6]+dp[2][5]+dp[2][4]+dp[2][3]
dp[3][8] = dp[2][7]+dp[2][6]+dp[2][5]+dp[2][4]
dp[3][9] = dp[2][8]+dp[2][7]+dp[2][5]+dp[2][6]
```
有沒有發現一件事情，就是從`dp[3][7]`到`dp[3][8]`，其值只是少了`dp[2][3]`，多了`dp[2][7]`，而`dp[3][9]`也有類似的關係。
如果依照這樣的思路推廣，那麼要算`dp[i][j]`的時候，其實只要計算`dp[i][j-1] - dp[i-1][j-1-F] + dp[i-1][j-1]`就好了，而不必算`dp[i-1][j-1] + dp[i-1][j-2]...`。
以六面骰為例:
就很像在「移動窗戶」一樣，在算下一個值的時候，只需要把尾端縮回來、頭往前延伸，而不必整個區間重算。(英文關鍵字: sliding window)
如此一來，計算`dp[i][j]`的時候，便只需要一加一減；而之前的算法，則是每次都需要算`F`個數字的和！
```cpp=
long long dp[2][3005];
long long slidingDP(int n, int m, int f) {
fill(dp[0], dp[0]+3005, 0);
fill(dp[0]+1, dp[0]+1+f, 1);
for (int i=1; i<n; ++i) {
long long cur = dp[0][i];
for (int j=i+1; j<=m; ++j) {
for (int k=1; k<=f; ++k) {
dp[1][j] = cur;
cur -= gv(j-f); //扣掉尾端
cur += dp[0][j]; //加入前端
cur %= MOD;
}
}
swap(dp[0], dp[1]);
fill(dp[1], dp[1]+3005, 0);
}
return dp[0][m];
}
```
時間複雜度: $O(NM)$
:::
Sign in with Wallet
Connect another wallet