<style> .reveal .slides { text-align: left; font-size:32px; } </style> # 計數&機率&Digit DP Introduction to Competitive Programming 4/24 --- - Classic DP Problems - p-median problem - Counting DP - 爬樓梯 - 走方格的路徑數 - 複習組合 - Digit DP (數位 DP) - Probabilistic DP - 骰子 - 抓老鼠例題 --- ## p-median problem 在線上有 $n$ 個點，選 $k$ 個線上的位置當成聯絡點，使得每個點到最近的聯絡點的距離和最小。  ---- 假設只能放一個聯絡點，那很明顯就是放中位數上。 如果 $n$ 是偶數，那放最中間的兩個數間距離總和都會是最小的。  ---- 並且我們知道每個點都會找離自己最近的聯絡點  所以不會發生這種交叉的事。 ---- 所以每個聯絡點負責的點們剛好會是序列上的連續區間。 並且對於每個的連續區間內都會是只有一個聯絡點的 case。  所以其實我們可以把問題變成，把 $n$ 長度的序列切成 $k$ 個連續的區間，且每個區間內各自的成本我們知道是中位數到所有點的和，加起來就是目前分割的答案了。 ---- 轉移: 大想法就是窮舉最後一個區間的左界 ```cpp= vector<int> A(n+1); d[j][i] = //區間[j,i]在只有一個聯絡點下的距離總和。 for(int h = 1; h <= k;++h){ //窮舉目前放了多少個區間 for(int i = 1;i <= n;++i){ // 1-base 第 h 個區間以 i 為右界 dp[h][i] = inf; //初始化 for(int j = 1; j <= i; ++j){ //第 h 個區間的左界 dp[h][i] = min(dp[h][i],dp[h-1][j-1] + d[j][i]); } } } cout << dp[k][n]; ``` ---- 練習一下回朔 [HW A](https://vjudge.net/contest/711384#problem/A) 距離要想一下 [HW B](https://vjudge.net/contest/711384#problem/B) pB hint : 單峰函數疊加完還是單峰函數 --- ## 計數DP 顧名思義，就是用 DP 來數數。 舉個例子 你在爬樓題每次可以爬 $1$ 階或直接跳 $2$ 階，到第 $N$ 階樓梯有幾種爬法？ 想必大家高中都學過如何數這個樓梯走法 $dp[i]=dp[i-1]+dp[i-2]$ 把它放到 DP 上就是遞迴式變轉移而已。 棋盤走路計數也跟樓梯差不多 [詳情](https://hackmd.io/@LeeShoWhaodian/HyjsE1soi#/6/5) ---- 棋盤走路計數問題 (有障礙物) 給定一個 $n * m$ 的棋盤$(1\le n,m < 10^5)$，棋盤上有 $N (1 ≤ N ≤ 2000)$ 個格子是黑色的，其他是白色的 初始位置在 $(1,1)$，只能向下或向右移動，也就是 $(i,j) \rightarrow(i+1,j) \ or \ (i,j) \rightarrow(i,j+1)$，且不能經過黑色的格子 問從 $(1,1)$ 移動到 $(n,m)$ 一用有多少種走法？ 跟棋盤走路計數一模一樣，只是多了障礙物不能走到。 ---- 可以發現，若不考慮黑格子(沒有黑格子)，則可以寫出 $dp[i][j]=dp[i-1][j]+dp[i][j-1]$ $(i,j)$ 能從 $(i-1,j) \ or \ (i,j-1)$ 來 然後其實就相當於 $\frac{(n+m)!}{n!m!}$ 等價 $n$ 個向下的箭頭(相同)和$m$ 個向右的箭頭排列(相同)。 那既然我們知道總和之後，就可以轉化問題為 "剛好經過一個黑格子的走法有幾種?" 這時就可以假設終點也是黑格子，則此問題在終點的答案就會剛好是原問題的答案。 ----  假設我們要算點從 $(0,0)$ 走到 點D，恰巧只經過一個黑點 (畫面上的點都是黑點) 的方法數， 那對 點D 而言，就是不能經過 點A、B、C (E不可能經過)。 ---- 那假設我們知道 點A、B、C在只經過一個黑點的方法數(也就是dp值)，那我們就能寫出以下轉移: $cnt(R,P) = \frac{(x[P] - x[R] + y[P] - y[R])!}{(x[P]-x[R])!(y[P]-y[R])!}$ 點 R 走到點 P 的全部方法數。 $dp[D] = cnt(O,D) - \sum^k_{\{A,B,C\}}{cnt(k,D)*dp[k]}$ 為啥不用考慮經過兩個黑點甚至以上的方法數? 我們知道 $dp[D] = cnt(D) - \#(到D至少經過一個黑點的方法數)$ 我們不妨窮舉這個至少經過的點 (也就是 A、B、C) ----  落在紅框的點為對此點而言就是到自己可能會經過的點。 由於 A 框內不包含任何點，所以 $sum += cnt(A,D) * dp[A]$ 是個對目前合法的計數。 那 B 框包含了點 A ，但 $dp[B]$ 照定義而言是走到 $B$ 不包含 $A$ 的方法數，所以 $cnt(B,D) * dp[B]$ 跟 $cnt(A,D) * dp[A]$ 是互斥的，所以我們也能放心加。 ---- 所以這個 $\#(到D至少經過一個黑點的方法數)$ 就會剛好是所有能到 $D$ 的點的 $cnt*dp$ 加起來。 那麼一個點 $P$ 而言，所有能到自己的點其 $x \leq x[P]$ 且 $y \leq y[P]$。 那這樣不會是 well-ordering 的，我們要怎麼決定轉移順序? ---- 對於點 $P$ 而言，他要轉移時 $x \leq x[P]$ 且 $y \leq y[P]$ 的點，都要先轉移完， 那對於 $x \leq x[P]$ 但 $y > y[P]$ 的點我們可以忽略，所以把點先按照 $x$ 排序，再按照 $y$ 排，這樣的轉移順序就合理了。 ---- Code: ```cpp= vector<pair<int,int>> A(N); sort(A.begin(),A.end()); //c++內建的pair排序就會先按照第一維升序排，若相等再由第二維升序排。 A.insert(A.begin(),pair<int,int>{1,1}); //塞起點 A.PB(pair<int,int>{n,m});//塞終點 vector<int> dp(N+5); for(int i = 1; i <= N+1;++i){ dp[i] = cnt(0,i); auto [x,y] = A[i]; for(int j = 1; j < i;++j){ auto [xx,yy] = A[j]; if(xx <= x && yy <= y) dp[i] -= cnt(j,i) * dp[j]; } } cout << dp[N+1]; //記得數字太大要好好模 ``` ---- 怕你忘記 cnt 怎麼實作，這邊複習一下組合常用模板: ```cpp= using i64 = long long; const i64 mod = 1e9+7; const int mxn = 2e5+5; i64 fac[mxn]; i64 fpow(i64 a,i64 b){ i64 ret = 1; for(;b;b>>=1,a=a*a%mod) if(b&1) ret = ret * a % mod; return ret; } i64 inv(i64 a){ //模乘法逆元 return fpow(a,mod-2); } i64 comb(i64 n,i64 m){ //組合數 C n 取 m return fac[n] * inv(fac[n-m]) % mod * inv(fac[m]) % mod; } fac[0] = 1; for(int i = 1; i < mxn;++i) fac[i] = fac[i-1] * i % mod; ``` ---- 所以我們的 cnt(i,j) 就會長 ```cpp= i64 cnt(int i,int j){ int dx = A[j].first - A[i].first; int dy = A[j].second - A[i].second; return comb(dx+dy,dy); } ``` ----  --- ## Digit DP 泛指在某種進制下 (當然常用就是10進制或2進制)，利用每一位放什麼當狀態來做轉移的DP。 問題通常都是處理某範圍下，像問 $[l,r]$ 區間內有多少個數字符合給定的條件，通常這種的問題$l、r$範圍可以很大，像 $10^{18}$ 或 $10^{20000}$ 之類的。 ---- 舉例: 假設我們想數 $[0,R]$ 內所有數字 (二進制)，他們的 1 的總和。 我們知道可以有更簡單的作法 (直接算每一位 1 出現的個數)，但這裡先複雜一下。 $dp[i][j][k] \ 放到第 \ i \ 位時，j \ 表示第 \ i \ 位是 \ 0 \lor 1$ $且 \ 1 \ 為 \ k \ 個的數字的個數。$ ---- 我們還有個數字要 $\leq R$ 的條件，所以多一維， $dp[i][j][l][k]$，$l = \ 0 \lor1 \ 表示有沒有貼著 R$ 什麼叫做貼著$R?$ ----  對於一個$\leq R$的數字如果它在目前位數的前面 (高位) 有任何一位 $<R$ 的那一位，那麼它就不貼著 $R$ ，也就是說對這個目前的數字而言，後面的位數無論放什麼都會使它 $<R$。 否則如果它貼著$R$ (也就是在目前位數前面，全部都跟$R$的相對位數相等)，那麼目前的位數就不能放超過對應 $R$ 的位數。 ----  像這樣就超過 $R$ 了。 也就是通過 $[l]$這維，我們能夠處理 $\leq R$的問題，但這時轉移順序就得從高位到低位。 ---- 假設 $R < 2^{32}$ 轉移: ```cpp= dp[32][0][0][0] = 1; //初始化(假想最左邊有個0) for(i = 31; i >= 0; --i){ //從高位開始轉移 auto &prv = dp[i+1]; //簡寫 prv[j][l][k] = dp[i+1][j][l][k]; auto &cur = dp[i]; int x = (R>>i)&1; // R的第 i 位 for(int k = 0; k <= 32; ++k){ //最多 32 個 1 for(int a = 0; a <= 1;++a){ //這位放 1 v 0 //沒有貼著 R 的可以從前面就沒貼著的轉移 cur[a][0][k + a] += prv[0][0][k] + prv[1][0][k]; if(a < x){ //或這位開始小於 R 所以可以從前面貼著的轉移 cur[a][0][k + a] += prv[0][1][k] + pre[1][1][k]; } if(a == x){ //貼著 R 的只能從前面就貼著 R 的轉移 cur[a][1][k + a] += prv[0][1][k] + pre[1][1][k]; } } } } int ans = 0; for(int i = 0; i <= 1;++i){ for(int j = 0; j <= 1;++j){ for(int k = 0; k <= 32;++k){ ans += dp[0][i][j][k] * k;//算答案 } } } cout << ans; ``` ---- 複雜度: 空間: $O(lg(R)*2*2*lg(R))$ 時間: 跑完所有狀態所以同上。 ---- [再一個例題](https://atcoder.jp/contests/dp/tasks/dp_s): 計算 $[1,K]$ 中(10進制)數位和是 $D$ 的倍數的個數。 - $1\leq K \leq 10^{10000}$ - $1 \leq D \leq 100$ ---- 老樣子 $D$ 很小，很明顯能當狀態。 $dp[i][j][l][d]$ 放到第 $i$ 位，放 $j$ ，且 $l=$ 有無貼著 $K$ 且位數和 $mod \ D$ = $d$ 的數字的個數。 但其實我們不需要知道前一位放什麼就能轉移了，所以 $dp[i][l][d]$ 就好 ---- 轉移: ```cpp= string K; int D; cin >> K >> D; reverse(all(K)); //從高到低 dp[K.size()][1][0] = 1; for(int i = K.size() - 1; i >= 0; --i){ auto &prv = dp[i+1]; auto &cur = dp[i]; int x = K[i] - '0'; for(int a = 0; a <= 9; ++a){ //窮舉這位放什麼 for(int d = 0; d < D;++d){ cur[0][(d + a) % D] += prv[0][d]; if(a < x){ cur[0][(d + a) % D] += prv[1][d]; } if(a == x){ cur[1][(d + a) % D] += prv[1][d]; } } } } //題目要求 >= 1 ，所以要 -1 cout << (dp[0][1][0] + dp[0][0][0] - 1) << '\n'; //記得模 :D ``` --- ## 機率 DP 跟計數很像，就是把機率丟到DP上做轉移。 也可以是在計數，把該事件的方法數算出來後再除，這樣也是機率，但問題在如果有條件機率或其他情形下，直接拿機率進行轉移會更方便。 ---- ## 例題: [骰子](https://cses.fi/problemset/task/1725) 一顆六面骰子，擲 $n$ 次後，所有結果相加 (1~6) 落在$[a,b]$間的機率? - $1 \leq n \leq 100$ - $1 \leq a \leq b \leq 6n$ $6n$ 最多才 $600$ 很明顯能當狀態。 ```cpp double dp[N+1][6*N+1]; // dp[i][j] 擲了 i 次，和是 j 的機率。 for(int i=1;i<=6;i++){ dp[1][i]=1.0/6.0; //初始化 } ``` ---- 在擲到第 i 輪，且點數和不同的機率間是互斥的，所以可以分開加 (轉移)。 轉移: ```cpp= for(int j = 2; j <= n;++j){ for(int w = 1; w <= 600;++w){ for(int i = 1; i <= 6;++i){ //第 j 次擲出 i 點 dp[j][w] += dp[j-1][w-i]; //dp[j-1][w-i] / 6.0 (擲到 i 就是 1/6.0) } dp[j][w] /= 6.0; // 一次除 避免不必要的精度誤差 } } ``` ---- ## 例題: [抓老鼠](https://codeforces.com/problemset/problem/148/D) 袋子裡有 $w$ 隻白鼠和 $b$ 隻黑鼠，公主和龍輪流從袋子裡抓老鼠。誰先抓到白色老鼠誰就贏，如果袋子裡沒有老鼠了並且沒有人抓到白色老鼠，那麽算龍贏。公主每次抓一隻老鼠，龍每次抓完一隻老鼠之後會有一隻老鼠跑出來。每次抓的老鼠和跑出來的老鼠都是隨機的。公主先抓。問公主贏的機率。 - $0\leq w,b \leq 1000$ 同理，這數字很小能當狀態，不妨考慮 $dp[i][j]=$白老鼠是 $i$ 隻 黑老鼠是 $j$ 隻公主贏的機率。 ---- 然後在每輪分一下 Case。 一輪就是公主抓一隻，龍抓一隻。 $i$ 隻白鼠，$j$ 隻黑鼠時: <div style="font-size:23px;position: absolute; right: 10%;"> - 在本輪結束 1. 公主直接抓到白鼠，公主贏了。 機率為 $\frac{i}{i+j}$ 2. 公主抓到一隻黑鼠，龍抓到一隻白鼠，龍贏了。 機率為 $\frac{j}{i+j}\cdot \frac{i}{i+j-1}$ - 本輪結束後繼續，所以必定是公主和龍都抓到黑鼠 - 公主和龍都各抓到一隻黑鼠 機率為 $\frac{j}{i+j}\cdot\frac{j-1}{i+j-1}$ 3. 且抓完後跑出來一隻黑鼠，接下來從 $dp[i][j-3]$ 轉移過來。 機率為 $\frac{j}{i+j}\cdot\frac{j-1}{i+j-1}\cdot\frac{j-2}{i+j-2}$ 4. 且抓完後跑出來一隻白鼠，接下來從 $dp[i-1][j-2]$ 轉移過來。 機率為 $\frac{j}{i+j}\cdot\frac{j-1}{i+j-1}\cdot\frac{i}{i+j-2}$ </div> ---- 那由於我們是要問公主贏的機率，所以不需要計算第二種狀況(也就是龍贏的情況)。 ```cpp using ld = long double; ld dp[1005][1005]; // 初始化 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++) { auto &cur = dp[i][j]; cur += (ld)i/(i+j); //Case 1 ld x = (ld)j/(i+j) * (j-1)/(i+j-1); //都抓到黑的機率 if(j >= 3) cur += x * (j-2)/(i+j-2) * dp[i][j-3]; // 黑的跑走 if(j >= 2) cur += x * i/(i+j-2) * dp[i-1][j-2]; // 白的跑走 } } ``` --- [題單](https://vjudge.net/contest/711384#overview)