<style> .reveal .slides { text-align: left; font-size:28px; } </style> # DP and Combination Introduction to Competitive Programming 4/12 ---- ## Outline - Classic DP Problems - Largest Sum Contiguous Subarray - LCS vs LIS vs Edit distance - subset sum & bitset 優化 & 二進制拆解 - 01背包 vs 無限背包 vs 有限背包 - p-median problem - Counting DP - 爬樓梯 - 走方格的路徑數 - Combination - 排列 - 組合 - 二項式定理 (Binomial theorem) - Probabilistic DP - 骰子 - 抓老鼠例題 --- ## 經典DP題目 ---- ## 最大連續區間和 問題敘述 : 已知每個賭局最大可以贏得多少錢，以正數與負數表示表示贏錢與輸錢 請問在連續的賭局當中最多可以贏得多少錢 題目的意思等價於求一個序列中子序列的最大連續和 分析每個 $arr_i$ 會發現只有兩種情況，一種是包含在答案的子序列中(必須是連續的)，另一種是它是新的連續子序列的開頭。 而其中不包含在答案的子序列中就不必討論，只討論包含在答案的子序列中。 ---- 可以把 $dp[i][j]$ 定義成表示第 $i$ 項在兩種情況當中前 $i$ 項的最大連續和 其中 $j$ 代表前頁的第幾種情況 若 $j=0$ 代表第 $i$ 項包含在答案的子序列中 若 $j=1$ 代表第 $i$ 項是新的連續子序列的開頭 則可以求出轉移式 $$ \begin{cases} dp[i][0] = max(dp[i-1][0], dp[i-1][1]) + arr[i] \\ dp[i][1] = arr[i] \end{cases} $$ 初始化 $$ \begin{cases} dp[0][0] = 0 \\ dp[0][1] = arr[0] \end{cases} $$ ---- 為何是 $$ \begin{cases} dp[i][0] = max(dp[i-1][0], dp[i-1][1]) + arr[i] \\ dp[i][1] = arr[i] \end{cases} $$ 因為對於 $dp[i][0]$(這一項必取) 來說，它包含前幾項的最好，所以它會是 $dp[i-1][0]$(前一項也取) 或者是 $dp[i-1][1]$(前一項是第一項) 的 $max$ 加上他自己 而對於 $dp[i][1]$ 來說，他自己就是第一項，因此它的值 (對第 $i$ 項來說 $i$ 就是第一個) 會是 $arr[i] + 0$ ---- ## bonus 同時會發現到dp轉移式裡面只轉移 $i$ 以及 $i-1$ ，根據我們之前所說的，這可以使用 rolling 壓縮空間複雜度，因此會變成這樣。 ```cpp dp[i&1][0] = max(dp[(i-1)&1][0], dp[(i-1)&1][1]) + m; dp[i&1][1] = m; ``` 而時間複雜度會是$O(n)$ --- ## LCS vs LIS vs Edit distance LCS : 最長共同子字串 詳情見上次 [dp講義](https://hackmd.io/@LeeShoWhaodian/HyjsE1soi#/5/6) LIS : 最長遞增子字串 詳情見上次 [dp講義](https://hackmd.io/@LeeShoWhaodian/HyjsE1soi#/5/9) Edit distance : 最短編輯距離 本日重點 * LCS to LIS * Edit distance * 三種 dp 進行比對 ---- 在那之前要先補充二分搜的 $LIS$ 作法  從 $1$ 到 $n$ 遍歷 $A$ 的每個元素，每次與 $X$(當前LIS) 裡的元素進行檢查， 若是比結尾元素大就加入，若沒有就使用 $lower\_bound$ 取代原本的位置。 ---- ### sample code 從 $1$ 到 $n$ 遍歷 $A$ 的每個元素，每次與當前 LIS 裡的元素進行檢查， 若是比結尾元素大就加入，若沒有就使用 $lower\_bound$ 取代原本的位置。 ```cpp= vector<int> getLIS(vector<int> a){ vector<int> lis; for(int i : a){ if(lis.empty() || lis.back() < i) lis.push_Back(i); else *lower_bound(lis.begin(), lis.end(), i) = i; } return lis; } ``` ---- ## LCS to LIS 為何需要轉換? * 求出 LCS 的時間、空間複雜度都是 $O(N^2)$ ，使用滾動陣列技巧，可將空間複雜度降至 $O(N)$ * 求出 LIS 的時間複雜度 $O(N^2)$ ，空間複雜度 $O(N)$ ，但其中 LIS 的時間複雜度可以使用二分搜 (lower_bound) 優化成 $O(N\log N)$ 怎麼轉換? * LIS 轉 LCS ：令原序列 A 排序後變成 B 。 A 和 B 的 LCS ，就是 A 的 LIS 。 * LCS 轉 LIS ：將序列 A 和 B 當中的相同字母配對通通找出來，表示成位置數對，以特殊規則(Counting sort)排序，然後找到 LIS ，就是 A 和 B 的 LCS 。 ---- LCS 轉 LIS 於是你會發現二維平面的 LCS 會變成二維平面的 LIS  ---- 二維平面的 LIS 聽起來複雜度並沒有比較好，因此 所有數對：第一維由小到大排序；當第一維平手，則第二維由大到小排序。 排序之後，原本數對們的 2D LIS ＝第二維的 1D LIS 於是就可以將LCS在經過一連串的預處理之後變成 $O(n \log n )$ 的時間複雜度。  ---- ## Edit distance ex : $string_1$ : horse $string_2$ : ros 所謂 Edit distance 就是 $string_1$ 最少要幾步才能變成 $string_2$ ，而其中每一步可以是 “新增”、“刪除” 或是 “取代”。所以第一個範例 horse 經過了 1. 用 r 取代 h 2. 把中間的 r 刪除 3. 把最後的 e 刪除 就可以得到 ros ，共花了 3 步 (3 就是答案)。 ---- 通常如果是需要去比對兩個字串的題目，我們會定義狀態為一個二維陣列 $dp[i][j]$ $dp[i][j]$ 為 $string_1$ 中前 $i$ 個字元的字串和 $string_2$ 中前 $j$ 個字元的字串的 Edit Distance 而我們知道子問題後，我們的答案就顯而易見是 $dp[len(string_1)][len(string_2)]$ 而很重要的初始化會發現，每個字串到空字串之間最快的路徑就是直接"消除"，因此會有以下初始化 : $$ \begin{cases} dp[i][0] = i \ , i \leq len(string_1)\\ dp[0][j] = j \ , j \leq len(string_2)\\ \end{cases} $$ ---- 然後我們只需要思考， $dp[i][j]$ 可以怎麼轉移。 分別有兩點 * 當 $string_1$ 第 $i$ 個字和 $string_2$ 第 $j$ 個字相同時，則 $dp[i][j] = dp[i-1][j-1]$ ，因為此時不需要做任何操作即相同。 * 當 $string_1$ 第 $i$ 個字和 $string_2$ 第 $j$ 個字不同時，則會有三個操作 1. 刪除 : 刪除第 $i$ 個字，此時 $dp[i][j]$ 為 $dp[i-1][j]+1$ (後面的 +1 代表刪除) 2. 新增 : 新增第 $i$ 個字，此時 $dp[i][j]$ 為 $dp[i][j-1]+1$ (後面的 +1 代表新增) 3. 取代 : 把 $string_1$ 的第 $i$ 個字變成 $string_2$ 的第 $j$ 個字，此時 $dp[i][j]$ 狀態方程為 $dp[i-1][j-1]+1$ (後面的 +1 代表取代)。 所以可以總結出狀態轉移方程為 $dp[i][j]= min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])+1$ ---- ## LCS vs LIS vs Edit distance || $\texttt{時間複雜度}$ | $\texttt{空間複雜度}$ | $\texttt{狀態轉移式}$ | |:-------------:| --------- | ----- | ------------- | | LIS | $n\log n$ | $n$ | $\texttt{max(dp[i],dp[j]+1)}$ | | LCS | $n^2$ | $length(str_1)$ | $\texttt{dp[i-1][j-1]+1}$ or $\texttt{max(dp[i][j-1], dp[i-1][j])}$ | | Edit distance | $n^2$ | $length(str_1)$ | $\texttt{min(dp[i][j-1]},\\ \texttt{dp[i-1][j]},\\ \texttt{dp[i-1][j-1])+1}$ | --- ## subset sum 給一個陣列 ex : {3, 34, 4, 12, 5, 2}, sum = 9 如果裡面的數字挑選幾個出來，相加等於 9 就代表符合這個問題。 ---- 首先會思考到，由於只能挑跟不挑，所以可以暴力枚舉每一個數字是否再答案裡面，然後再思考一下時間複雜度就會發現，需要的量級是指數級的，為 $O(2^n)$ 所以 $n$ 稍微大一點就很容易TLE 所以會需要使用到動態規劃，令 $dp[i][j]$ 表示 $arr$ 中前 $i$ 個元素的子集和等於 $j$ 的情況，則 若 $arr[i] > j$ ，則 $arr[i]$ 不在子集 $subset$ 中。 若 $arr[i] \le j$ , 則有以下兩種情況：一種情況是 $arr[i]$ 不在子集 $subset$ 中，則 $dp(i, j) = dp(i-1, j)$ 一種情況是 $arr[i]$ 在子集 $subset$ 中，則 $dp[i][j]= dp[i-1][j-arr[i]]$ 這樣就有了這個問題的子結構問題，因此，只需要確定初始情況即可 而初始情況即為對於 $i=0,1,2,...,n$ ,有 $dp[i][0]=True$ , 對於 $j=1,2,...,M$ , 有 $dp[0][j]=False$ ---- 然後你就會發現代碼會長這樣 ```cpp for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(j<arr[i]) dp[i][j] = dp[i-1][j] else dp[i][j] = dp[i-1][j] | dp[i-1][j-S[i-1]] ``` 而倘若你需要知道 subset 是由那些 sub_element 組合成的，則可以把 DP 的真值表印出來，參考上次 LCS 的回朔法使用查詢。 [參考甲文](https://www.cnblogs.com/jclian91/p/9132663.html) ---- ## 0/1背包 bitset 優化 例題 : [zerojudge a416](https://zerojudge.tw/ShowProblem?problemid=b951) 題目敘述轉化 : 把一列大小為 $n$ 整數序列分成兩個子集且讓兩個子集的 sum 最接近 那這邊我們就可以用到 bitset 的思想，首先先介紹一下 bitset 的用法和為何使用 bitset : * 對於 bitset，它儲存的是二進制數位。 * bitset 就像一個 bool 類型的陣列一樣，但是有空間優化：bitset 中的一個元素只占 1 bit，相當於一個 char 所占空間的八分之一。 * bitset 中的每一個元素都可以被單獨存取，例如一個叫做 foo 的 bitset，foo[3] 存取了它的第四個元素，這點類似於陣列。 * bitset 有一個特性：整數類型和 bool 陣列都可以轉化為 bitset。 * bitset 的大小在編譯前就需要確定 (程式碼中使用常數宣告大小) 。 [更多具體用法以及魔法](https://www.cnblogs.com/RabbitHu/p/bitset.html) ---- 對於這道題，我們用 bitset 來替代 DP，bits[j] 的含義與 DP[j] 的含義相同。就是是否有這樣的一個子集的總和是 $j$ 假設現在有一個數組 {2,3,5,2,3,5} 很明顯可以看出它的解答是 $2+3+5=10$ 那對於我們的 bitset 數組會長這樣 ```cpp bitset<N> dp(1); dp {1} //代表0可以選 (有一個子集合是0) dp {101} //加入'2' 了，把原本所有1的bit左移兩個 現在代表 '2' 和 '0' 都可以有子集合 dp {101101} //加入'3'了，把原本所有1的bit左移三個 '0' '2' '3' '5' 都有子集合 dp {10110101101} //加入'5'了，把原本所有1的bit左移五個 //依此類推 ``` 到最後只要詢問 $sum/2$ 開始往左右邊遍歷就可以知道答案了。 --- ## 下課時間 --- ## 二進制分解 <div style="font-size: 30px"> 其實每種物品有 $K$ 個，不需要 $K$ 種組合 $(1\sim K)$ 都做一次 我們只需要做 $\lfloor \log K \rfloor$ 次就好 分別捆成 1個、2個、4個、8個、16個、...、$2^{\lfloor \log K \rfloor}$ 以及剩下的 ($K -1 -2 -4 ... -2^{\lfloor\log K\rfloor}$) 這是一個 這些捆的組合，就可以湊出數量 $1\sim k$ 的所有物品 以數量為 9 為例 分成 1, 2, 4, 2 四堆 </div> 1=1 2=2 3=1+2 4=4 5=1+4 6=2+4 7=1+2+4 8=2+4+2 9=1+2+4+2 ---- K 個物品，拆成 log K 個 ```cpp vector<int> item; for(int i = 1; k>=i; i*=2){ item.push_back(i); k -= i; } item.push_back(k); ``` --- ## 01背包 vs 無限背包 vs 有限背包 每個背包都有一個耐重上限 $weight$ , 求在這個 $weight$ 裡最多可以裝多少 $value$ 的內容物 而對於 $dp[i]$ 的定義則是在耐重上限為 $i$ 的時候，可以裝的最大內容物價值為何。 01背包 : 每個物品只能選擇取或是不取 無限背包 : 每個物品都有無限個，可以取到死 有限背包 : 每個物品各自有 $K$ 個 依照題目給定 ---- ## 01背包 之前已經有教過例題了 詳情請看 [背包問題](https://hackmd.io/@LeeShoWhaodian/HyjsE1soi#/5/3) 而0/1背包的實作代碼大略會長成這樣 ```cpp for (int i = 1; i <= cnt; i++) //幾個物品 for (int j = weight; j >= w[i]; j--) //從物品耐重上限枚舉到此物品的重量，代表每個都最多選一次 dp[j] = max(dp[j], dp[j - w[i]] + v[i]); ``` ---- ## 無限背包 之前作業有出過 可以去補一下 完全背包模型與 0/1 背包類似，與 0/1 背包的區別僅在於一個物品可以選取無限次，而非僅能選取一次。 於是與 0/1 背包在代碼上的差別就是，枚舉重量的時候不能從最大耐重枚舉回來，而是要從最小開始，因為這樣才會有讓物品被重複選取的機會。 ---- 而無限背包的實作代碼大略會長成這樣 ```cpp for(int i = 1; i <= cnt; i++) for(int j = w[i]; j <= weight; j++) dp[j] = max(dp[j], dp[j - w[i]] + v[i]); ``` ---- ## 有限背包(多重背包) 多重背包也是 0/1 背包的一個變式。與 0/1 背包的區別在於每種物品有 $k_i$ 個，而非一個。 一個很簡單的想法就是：把「每種物品選 $k_i$ 次」等價轉換為「有 $k_i$ 個物品，每個物品選一次」。這樣就可以轉換成 0/1 背包模型 然後套用 0/1 背包即可解。 但會發現一件事情，你會發現 0/1 背包的複雜度 $O(NW)$ 在有限背包會直接變成 $O(NWK)$ ，因此很明顯有些情況會超時，而且 $O(NW)$ 就是神聖且不可優化的一部份，所以我們只能想辦法優化 $K$ ，那就會需要剛剛所提到的二進制拆分。 把每個 $K$ 做二進制拆解，那時間複雜度就會從 $O(NWK)$ 下降成 $O(W \cdot \sum_{i=1}^n log_2 k_i)$ => $O(N \cdot W \cdot log_2 k)$ ---- 把有限背包二進制拆分的具體代碼 ```cpp index = 0; for (int i = 1; i <= m; i++) { int c = 1, p, h, k; cin >> p >> h >> k; while (k > c) { k -= c; list[++index].w = c * p; list[index].v = c * h; c *= 2; } list[++index].w = p * k; list[index].v = h * k; } ``` 然後再去做0/1背包即可 ---- 另外還有一種是混合背包，每一種物品可能是只有一個，有 $K$ 個，或者是有無限個，那其實也不用被這種類型的題目嚇到，只需要這樣做即可。 ```cpp for (循環物品種類) { if (是 0 / 1 背包) 套 0 / 1 背包代碼; else if (是無限背包) 套無限背包代碼; else if (是有限背包) 套有限背包代碼; } ``` ---- <div style="font-size:25px;position: absolute; right: 8%;"> | $\texttt{種類}$ | $\texttt{時間複雜度}$ | $\texttt{空間複雜度}$ | $\texttt{狀態轉移式}$ | $\texttt{順序以及步驟}$ | |:-------------:| --------- | ----- | ------------- | ------ | | 0/1背包 | $NW$ | $N+W$ | $\texttt{max(dp[j],dp[j-w[i]]+v[i])}$ | 從 $W$ ~$w_i$ | | 無限背包 | $NW$ | $N+W$ | $\texttt{max(dp[j],dp[j-w[i]]+v[i])}$ | 從 $w_i$ ~$W$ | | 有限背包 | $NWlogk$ | $N log K + W$ | $\texttt{max(dp[j],dp[j-w[i]]+v[i])}$ | 二進制拆分後從 $W$ ~$w_i$ | </div> --- ## p-median problem [例題](https://zerojudge.tw/ShowProblem?problemid=e165) 題目敘述轉換 : 給你 $n$ 個點，然後選擇其中 $k$ 個點當作重點，使得每個點到最近的重點的距離為小。  ---- 老樣子可以先簡化問題，思考他只有一個重點，或是只有一個點的時候會發生什麼事情。 然後就會發現可以把問題簡化成  然後就會發現 p-Median Problem 就變成了如何分區的問題，只要分好區然後選擇每個區的中位數就會是對的。 ---- $N$ 為點個數， $P$ 為重點個數。總共 $O(NP)$ 個子問題，計算一個子問題需時 O$(N)$ ，時間複雜度 $O(N^2P)$ 。 $dp[i][j]$ 代表當今天只有前 $j$ 個點，有 $i$ 個重點的時候答案是多少。 $d[i][j]$ 各種區域，其聯絡距離的總和。 $r[i][j]$ 記錄最佳的分界線(分區)位置。 ```cpp void p_Median(){ for (int i=1; i<=N; ++i) for (int j=i; j<=N; ++j){ m = (i+j)/2,d[i][j] = 0; // m是中位數，d[i][j]為距離的總和 for (int k=i; k<=j; ++k) d[i][j] += abs(arr[k] - arr[m]); } for (int p=1; p<=P; ++p) for (int n=1; n<=N; ++n){ dp[p][n] = 1e9; for (int k=p; k<=n; ++k) if (dp[p-1][k-1] + d[k][n] < dp[p][n]){ dp[p][n] = dp[p-1][k-1] + d[k][n]; r[p][n] = k; // 從第k個位置往右到第j個位置 } } } ``` ---- 可用凸包加速到 $O(NP)$ 但不是本堂課重點 跳過。 然後這題沒出作業，想鞏固一下知識點的可以去寫這題 [UVA 662](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=603) 他需要遞迴輸出路徑 小難 --- ## 計數DP 特點是很像數學題，總會混合一點數學的概念在裡面 最簡單的問題 [爬樓梯](https://oj.leo900807.tw/problems/22) 每次可以只爬 $1$ 階或直接跳 $2$ 階，到第 $N$ 階樓梯有幾種爬法？ 應該可以很直覺的寫出這個式子 $dp[i]=dp[i-1]+dp[i-2]$ 若我們對這個式子做出進一步的探討，會發現他就是記錄到每一階的走法有幾種，然後把紀錄的走法每次加起來，而這其實就是計數問題。 而上次也講解了另外一題走迷宮數量問題 [詳情](https://hackmd.io/@LeeShoWhaodian/HyjsE1soi#/6/5) ---- 經典題目 : 二階樓梯計數問題 (有障礙物) 題目敘述 : 給定一個 $n * m$ 的棋盤$(1\le n,m < 10^5)$，棋盤上有 $N (1 ≤ N ≤ 2000)$ 個格子是黑色的，其他是白色的 初始位置在左上角，只能向下或向右移動，不能經過黑色格子 從左上角移動到右下角一用有多少種走法？ 跟二階樓梯一模一樣，只是多了障礙物不能走到。 ---- 可以發現，若不考慮黑格子(沒有黑格子)，則可以寫出 $dp[i][j]=dp[i-1][j]+dp[i][j-1]$ 然後其實就相當於 $C_{m}^{m+n}$ (每列要選擇要走哪一格，並且只能相鄰) 那既然我們知道總和之後，就可以轉化問題為 "經過黑格子的走法有幾種?" 這時就可以假設終點也是黑格子，因為我們可以利用每一個黑格子之間的關係去求出從起點走到黑格子的方案數 ---- 然後我們就可以開始定義我們的 $dp[i]$ 為，當走到第 $i$ 個黑格子且不經過其他黑格子時可以有多少種走法。 然後你就會發現 $dp[i]=C_{x_i-1}^{x_i-1+y_1-1} - \sum_{j=0}^{i-1} dp[j]\cdot C_{x_i-x_j}^{x_i-x_j+y_i-y_j}$ 然後我們只需要假設終點也是黑格子，求出到終點且不經過其他黑格子的方案數即可 於是就可以很輕鬆的算出作業的答案，那還有一個很大的問題，也就是我們要怎麼求出 $C_y^x$ 呢? --- ## 組合論 :-1: 哈哈是我啦 沒錯我們就是要使用組合論 以下是組合數的板子(qpow 要自己寫)，那套這個板子就可以過剛剛那一題了。 ```cpp ll fac[1'000'020],inv[1'000'020]; ll getInv(ll a){ return qpow(a,mod-2); } //逆元 void init(int n){ // O(N) fac[0] = 1; for(ll i = 1; i <= n; i++) fac[i] = fac[i-1] * i % mod; inv[n] = getInv(fac[n]); for(ll i = n-1; i >= 0; i--) inv[i] = inv[i+1] * (i+1) % mod; } ll C(int n,int m){ //O(1) if(m > n) return 0; return fac[n] * inv[m] % mod * inv[n-m] % mod; } ``` 複雜度 $O(N)$ 預處理， $O(1)$ 詢問 ----  ---- ## 排列 定義 : 從 $n$ 個不同元素中，任取 $m$ 個元素按照一定的順序排成一列，叫做從 $n$ 個不同元素中取出 $m$ 個元素的一個排列；從 $n$ 個不同元素中取出 $m(m\leq n)$ 個元素的所有排列的個數，叫做從 $n$ 個不同元素中取出 $m$ 個元素的排列數，用符號 $\mathrm A_m^n$（或者是 $\mathrm P_m^n$）表示。 排列的計算公式為: $\mathrm A_m^n=n(n-1)(n-2)....(n-m+1)= \dfrac{n!}{(n-m)!}$ 而其中當 $n==m$ 時，則是排列的特殊情況，也稱為 "全排列" 此時 $\mathrm A_m^n$ 的答案為 $n!$ ---- ## 組合 定義 : 從 $n$ 個不同元素中，任取 $m$ 個元素組成一個集合，叫做從 $n$ 個不同元素中取出 $m$ 個元素的一個組合；從 $n$ 個不同元素中取出 $m$ 個元素的所有組合的個數，叫做從 $n$ 個不同元素中取出 $m$ 個元素的組合數。用符號 $\mathrm C_m^n$ 來表示。 $\mathrm C_m^n= \dfrac{\mathrm A_m^n}{m!}= \dfrac{n!}{m!(n-m)!}$ ---- ## 二項式定理 (帕斯卡三角形) 這也是大家都上過的課程，其中 $(a+b)^n=\sum_{i=0}^{n} \mathrm C_i^n \cdot a^{n-i}b^i$ 而證明則可以使用數學歸納法證明。 ---- [二項式定理超難例題](https://codeforces.com/gym/102780/problem/J) 如果可以在賽中解出這題，就代表你的二項式定理超強。(還有python) 題目敘述 : 給出一個數 $x$ ，要求將其表示為不超過 $5$ 個數的立方和的形式， $x$ 範圍為 $10^{100000}$ 首先，會知道第一件事情，對於任何數字 $y$ ， $y - (y\%6)^3$ 之後， $y$ 必定為6的倍數。 ``` 1 - 1^3 = 0%6 == 0 2 - 2^3 = -6%6 == 0 3 - 3^3 = -24%6 == 0 4 - 4^3 = -60%6 == 0 5 - 5^3 = -120%6 == 0 ``` 所以我們的第一個數字就是 $(x\%6)$ 那這樣剩下的 $x-(x\%6)^3$ 就會是 $6$ 的倍數 ---- 然後通過二項式定理我們可以輕易地發現(湊出) : $(a-1)^3+(a+1)^3+(-a)^3+(-a)^3=6a$ 接著我們把 $a=x-(x\%6)^3$ 代進去(記得除$6$)，所以答案剩餘的四個數字會是 $\dfrac{x-(x\%6)^3}{6}+1 , \dfrac{x-(x\%6)^3}{6}-1, -\dfrac{x-(x\%6)^3}{6}, -\dfrac{x-(x\%6)^3}{6}$ 於是就可以得出答案為 $(x\%6), \dfrac{x-(x\%6)^3}{6}+1 , \dfrac{x-(x\%6)^3}{6}-1, -\dfrac{x-(x\%6)^3}{6}, -\dfrac{x-(x\%6)^3}{6}$ 因為範圍是 $10^{100000}$ 所以你算完這些之後需要使用 PYTHON or JAVA 求解，或是手刻大數運算。 --- ## 機率 DP 機率 DP 用於解決概率問題與期望問題，通常，解決機率問題需要順序循環，而解決期望問題使用逆序循環，如果定義的狀態轉移方程存在後效性問題，還需要用到高斯消元來優化。機率 DP 也會結合其他知識進行考察，例如 狀態壓縮，樹上進行 DP 轉移等。 不過今天只教最簡單的 入門版機率 DP 這類題目用順推，也就是從初始狀態推向結果。和一般的 DP 非常類似，難點依然是對狀態轉移方程的定義，只是這類題目經過了機率論知識的包裝。 ---- ## 簡單例題 [骰子](https://cses.fi/problemset/task/1725) 題目敘述 : 骰子。骰 $k$ 次，詢問總和在 $a\sim b$ 之間的機率是多少。 我們可以立即的給定一個 $dp[i]$ 為總和為 $i$ 的機率是多少。 首先很簡單會發現骰 1 次，對於 1~6 他們的機率分別都是 $\frac 1 6$ 所以我們的初始化就會是 ```cpp double dp[N+1][6*N+1]; for(int i=1;i<=6;i++){ dp[1][i]=1.0/6.0; } ``` ---- 然後我們只需要從第二次骰骰子開始做 dp 即可，每一次是加上可以從上一次轉移到自己的總和機率(也就是 1~6) 然後因為加了 6 個所以需要 /6 核心代碼 ```cpp for(int k=1;k<=6;k++){ dp[i][j] += dp[i-1][j-k]; } dp[i][j]/=6; ``` ---- ## 例題2 [抓老鼠](https://codeforces.com/problemset/problem/148/D) 題目大意：袋子裡有 $w$ 隻白鼠和 $b$ 隻黑鼠，公主和龍輪流從袋子裡抓老鼠。誰先抓到白色老鼠誰就贏，如果袋子裡沒有老鼠了並且沒有人抓到白色老鼠，那麽算龍贏。公主每次抓一隻老鼠，龍每次抓完一隻老鼠之後會有一隻老鼠跑出來。每次抓的老鼠和跑出來的老鼠都是隨機的。公主先抓。問公主贏的機率。 根據一些經驗，我們可以先定義 $dp[i][j]$ 為，當有 $i$ 隻白鼠和 $j$ 隻黑鼠時公主贏的機率。 ---- 然後思考一下每一輪會有以下四種情況 : <div style="font-size:23px;position: absolute; right: 10%;"> - 公主抓到一隻白鼠，公主贏了。 機率為 $\frac{i}{i+j}$ - 公主抓到一隻黑鼠，龍抓到一隻白鼠，龍贏了。 機率為 $\frac{j}{i+j}\cdot \frac{i}{i+j-1}$ - 公主抓到一隻黑鼠，龍抓到一隻黑鼠，跑出來一隻黑鼠，轉移到 dp[i][j-3]。 機率為 $\frac{j}{i+j}\cdot\frac{j-1}{i+j-1}\cdot\frac{j-2}{i+j-2}$ - 公主抓到一隻黑鼠，龍抓到一隻黑鼠，跑出來一隻白鼠，轉移到 dp[i-1][j-2]。 機率為 $\frac{j}{i+j}\cdot\frac{j-1}{i+j-1}\cdot\frac{i}{i+j-2}$ </div> ---- 那由於我們是要問公主贏的機率，所以不需要計算第二種狀況，且需要保證第三，第四種狀況的可能性 ```cpp #define ld long double for (int i = 1; i <= w; i++) dp[i][0] = 1; // 初始化 for (int i = 1; i <= b; i++) dp[0][i] = 0; for (int i = 1; i <= w; i++) { for (int j = 1; j <= b; j++) { dp[i][j]+=(ld)i/(i+j); if (j >= 3){ dp[i][j] += (ld)j/(i+j) * (ld)(j-1)/(i+j-1) * (ld)(j-2)/(i+j-2) * dp[i][j-3]; } if (i >= 1 && j >= 2) { dp[i][j] += (ld)j/(i+j) * (ld)(j-1)/(i+j-1) * (ld)i/(i+j-2) * dp[i-1][j-2]; } } } ``` --- ### 下周期中考 - 時間：4/19(三) 18:00-22:00 - 地點：203 教室 - 題數：8-10 題 - 範圍：開學到這星期為止內容 - 提供 Treap, PBDS, EXGCD, CRT 模板 - 單人單機 - 可以攜帶吉祥物、文具、紙本字典、空白計算紙 - 難度可以參考[去年記分板](https://codeforces.com/group/dnlUA4rsoS/contest/379764/standings)... - 建議把之前講義例題、作業、模擬賽都做過一遍 ---- ### Homework and Practice deadline: 4/19 link: https://vjudge.net/contest/551263