---
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`顆再骰到對應的點數。

    #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`中我們的遞迴函式，大約會長這樣:

  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
  }

從上面的圖可以發現，我們呼叫了許多參數完全相同的函式。這就像是，在數學考試中剛剛才花很多時間解完一題，下一題問你一模一樣的題目，你還再重算一次的意思是一樣的。

聰明的作法，是將答案記起來，之後如果有問到一樣的東西就不用重算了。

#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>

#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`顆骰的答案丟掉...

//計算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`個數字的和！

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)$

:::