<style> .reveal .slides { text-align: left; font-size:28px; } </style> # DP 優化 很難的DP 2/15 ---- * 單調隊列 * 矩陣快速冪 ---- 先簡單提到之前上課的內容: [例題](https://zerojudge.tw/ShowProblem?problemid=c528)： 給定一整數陣列，求取出數字的總和最大，且滿足相鄰兩數距離不能超過 $k$ 那很簡單 DP轉移式會變成這樣 $$dp[i] = arr[i] + max\{dp[i-1], dp[i-2], \dots, dp[i-k], 0\}$$ ---- 也就是說 要提出前一個到前 $k$ 個才可以求出下一個 那就很像是在求區間最大值，但求區間最大值有非常多方法 因為這題是連續求的，因此我們可以只記錄當前的區間  全部記錄下來 ----  我們就把最前面的移除掉，加入最新的，這樣就可以實現第一步 ---- 然後就會形成一個折線圖 (縱軸為value 橫軸為index)  然後就又可以發現，在上面這個圖中，$dp[i-k+1]$ 對任何人來說都是沒有用的 ---- 因為要取的是MAX，所以可以把不必要的東西剷除，於是會發現加入deque裡面的東西越來越少了。 然後會發現 $dp[i-k]$ 其實也是沒有用的，因為已經有一個最高點在他後面了 那我們好好解析這句話，也就是說我們的deque裡面任意點都不會存在後面有比他更高的點 也就是說 你的deque在這個例題裡面，會是單調遞減的。 ---- 那因為，你的deque是單調遞減的，所以每次取max的時候只需要求出頭的位置，即100%為答案所需，所以其複雜度為: 轉移只需要 $O(1)$ 取出 deque 的頭部 每個元素最多只會被 push 一次 pop 一次 所以總複雜度是 $O(N)$ ---- 詳情可以看 ```cpp= vector<pair<int, int>> deq(n + 5); int l = 0, r = 0; deq[l] = {0, 0}; for (int i = 1; i <= n; i++) { while (deq[l].second < i - k) l++; dp[i] = deq[l].first + arr[i]; while (l <= r and deq[r].first <= dp[i]) r--; deq[++r] = {dp[i], i} } ``` ---- ## 小結 所以單調隊列其實是一個很簡單的概念，就是使用資料結構去維護最大值(對答案最佳解)，來減少時間複雜度，代碼可能比較難懂但實際上懂了之後整件事情是簡單的。 核心:push的時候做單調性維護，而每次擴張邊界的時候對pop做邊界維護。使得頭永遠都是下一個DP項要找的MAX值。 ---- OK拉 直接看題目拉 ---- ## 例題 二維單調隊列 題意 : 給定矩陣的生成規則，求出在 $n*m$的矩陣中，每個 $a*b$ 大小矩陣的最小值的總和。 把一維的優化方法推演到二維是一個普遍的出題方式，所以這題就需要在二維平面上使用到單調隊列 ---- 思路 : 首先好好讀題目可以生成出值的陣列，然後先按照其中一個座標系，維護單調隊列，這樣就可以得到一個每 $a$ 間隔裡出現的 行/列 的區間最小值，而後再隊另外一個座標系去進行單調隊列維護，而第二次維護時要使用第一次的deque去進行更新，就可以每次找出區間最小值。 先找出每排的單調隊列長相(利用 $a$) -> 再找出每行的單調隊列，直接更新答案(利用$b$以及每排的單調隊列) --- # 矩陣快速冪 ---- 先複習一下矩陣乘法的程式碼 矩陣乘法程式碼： ```cpp= for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ for(int k = 0; k < n; k++){ ret[i][j] += a[i][k] * b[k][j]; } } } ``` ---- 例題： 環塗色 題序： 給兩個整數 n、$\lambda$， $\lambda$ 是有多少種顏色，n 是指有幾個頂點圍成的環，問你有幾種塗色方式可以讓環上連在一起的頂點兩兩顏色都不同 範圍：n、$\lambda \le 10^9$  n = 3, $\lambda$ = 3 以上為 6 種塗色方法 (1,2,3) (1,3,2) (2,1,3) (2,3,1) (3,1,2) (3,2,1) <!--  --> <!-- https://icpc2022.ntub.edu.tw/wp-content/uploads/2022/11/ICPC2022-main.pdf --> ---- 可以發現如果直接推的話，會長左下這樣，但是因為這樣很明顯無法知道最後一個的顏色是什麼，因此這個推法是錯的。  ---- 如果要正確推出多邊形有幾種塗色的方式，我們需要知道最後一個跟第一個不一樣的塗法有幾種，因此我們需要記錄每個節點跟第一個一樣及跟第一個不一樣的塗法 $color[i][0]$ 是指第 $i$ 個節點與第一個不一樣顏色的話有幾種塗法 $color[i][1]$ 是指第 $i$ 個節點與第一個一樣顏色的話有幾種塗法 ---- 轉移就會變成以下這樣 color[i][0] = color[i - 1][0] * ($\lambda$ - 2) + color[i - 1][1] * ($\lambda$ - 1) color[i][1] = color[i - 1][0] 而初始值是 color[0][0] = 0 color[0][1] = $\lambda$ (在第一個的時候顏色會跟自己一樣，因此是 $\lambda$) ---- 這樣就做完了嗎？ No，他的 k 的範圍最多到 $10^9$，除了沒辦法開那麼大的陣列以外，時間也不足以跑完 $10^9$，這時候就需要矩陣快速冪加速了。 ---- 推導過程： ${\begin{bmatrix} \lambda - 2 &\lambda - 1\\1&0 \end{bmatrix}}\quad \times \quad \begin{bmatrix} \text{color[0][0]}\\\text{color[0][1]}\end{bmatrix}$ <!--  --> ---- 通過以上的推導，我們就可以對求出的矩陣做快速冪，在 $O(log_2N)$ 的時間找出我們要的多邊形塗色的答案了，也就是 color[n - 1][0] (第 n 個跟第一個顏色不同的塗法)。 ---- ## 2022 ICPC  題意 : 給你三個數字 $n$ , $k$ , $\lambda$ 分別是中間的多邊形邊數，外擴的四邊形層數，顏色種數，詢問有幾種塗色方案(隔壁不能重複)。 ---- 知道了環內的選擇方法後外面就很簡單了，外面第一層就是 $k_{value} = \frac{1}{\lambda-1}*(\lambda-1)+\frac{\lambda-2}{\lambda-1}*(\lambda-2)$ 然後 $(k-1)*n*k_{value}*color[n-1][0]$ 就會是答案。 ---- ## 2023 TOPC 題意 : 給你 $a,b,c$ 符合 $x + \frac 1 x = a$ , 計算出 $x^b + \frac 1 {x^b} \mod c$ 那很直覺的方法是直接求解 $x$ 但那樣會有模空間下的問題以及反元素的問題，不過大多數隊伍依然使用此方式。 或是可以觀察求解，那就看一下怎麼做。 ---- 矩陣快速冪思路 : 因為我們沒辦法從$x^b + \frac 1 {x^b}$ 裡面看出任何東西，因此我們把她拆開來看 如果運算 $(x^{b-1} + \frac 1 {x^{b-1}}) * (x + \frac 1 x)$ 就會變成 $(x^{b} + \frac 1 {x^b})+(x^{b-2} + \frac 1 {x^{b-2}})$ 那也就是說 只需要把$(x^{b-1} + \frac 1 {x^{b-1}}) * (x + \frac 1 x)$ 減去 $(x^{b-2} + \frac 1 {x^{b-2}})$ 就會是我們的所求，那這樣就很像是費式數列的感覺了。 接著單看次方項就可以寫出以下式子 ---- ${\begin{bmatrix} a &-1\\1&0 \end{bmatrix}}\quad \times \quad \begin{bmatrix} f(b-1)\\f(b-2)\end{bmatrix} \quad = \quad \begin{bmatrix} f(b)\\f(b-1)\end{bmatrix}$ ---- 然後又因為矩陣的性質 所以又可以寫成這樣 ${\begin{bmatrix} a &-1\\1&0 \end{bmatrix}}^{b-1}\quad \times \quad \begin{bmatrix} f(1)\\f(0)\end{bmatrix} \quad = \quad \begin{bmatrix} f(b)\\f(b-1)\end{bmatrix}$ 又因為我們知道 $x^1 + \frac 1 {x^1} = a$ 以及 $x^0 + \frac 1 {x^0} = 2$ 所以又可以寫成這樣 ${\begin{bmatrix} a &-1\\1&0 \end{bmatrix}}^{b-1}\quad \times \quad \begin{bmatrix} a\\2\end{bmatrix} \quad = \quad \begin{bmatrix} f(b)\\f(b-1)\end{bmatrix}$ 最後計算左式即是答案。