<style> .reveal .slides { text-align: left; font-size:32px; } </style> # DP 計數 機率 Introduction to Competitive Programming 3/6 --- - Classic DP Problems - 二進制分解 - 01背包 vs 無限背包 vs 有限背包 - p-median problem - Counting DP - 爬樓梯 - 走方格的路徑數 - Combination - 排列 - 組合 - 二項式定理 (Binomial theorem) - Probabilistic DP - 骰子 - 抓老鼠例題 --- ## 二進制分解 <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; } if(k) 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)$ 但不是本堂課重點 跳過。 想鞏固一下知識點的可以去寫這題 [HW E](https://vjudge.net/contest/611787#problem/E) 他需要遞迴輸出路徑 小難 --- ## 計數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]; } } } ``` --- 作業 : https://vjudge.net/contest/611787#overview