<style> .reveal .slides { text-align: left; font-size:32px } </style> ## Bitmask DP 2025/5/8 --- - Bitmask DP - SOS DP --- ## Bitmask DP 又稱位元壓縮DP，泛指狀態是由二進制表示的DP。 通常可以表示集合，$0$ 就是不取，$1$ 就是取。 假設我有 $n$ 個東西要考慮，就能用一個長度為 $n$ 的bitstring表示，所以狀態通常會是 $O(2^n)$，看到題目範圍是 $\leq 20$ 這種就可以往 bitmask dp 想想看。 ---- 這邊先幫大家複習一下位元運算: ```cpp= x>>=1 //右移最左邊補零 x<<=1 //左移最右邊補零 //註 : k 0-base x&(1<<k) //取出 x 的第 k 位 if(x&(1<<k)) x = x ^ (1<<k) //把第 k 位歸零 x = x | (1<<k) //把第 k 位變成 1 x = ((1<<n) - 1) - x; //取 x 的補集合 //宇集 U = (1<<n) - 1 __builtin_popcount(x) //數 x 有幾個 1 ``` 使用位元運算要注意括號，位元運算比布林運算、算數運算優先度低，所以沒括號很容易爆掉。 其實 bitmask dp 就這樣，所以直接進例題。 ---- ### [搭電梯](https://cses.fi/problemset/task/1653) $n$ 個人排隊，每個人重 $w_i$ ，要搭一台負重 $x$ 的電梯，問你最少要搭幾趟?。 - $1 \leq n \leq 20$ - $1 \leq x \leq 10^9$ - $1 \leq w \leq x$ 很明顯的 $x$ 跟 $w$ 都不太能當狀態，畢竟到 $10^9$。 ---- 既然需要最少搭幾趟，不妨我們直接窮舉在一趟電梯中有哪些人上電梯。 假設 $n = 4,x=10$ $\ w=[4,8,6,1]$ ```cpp= 0 1 2 3 sum 0 0 0 0 -> 0 0 0 1 1 -> 7 0 1 0 1 -> 9 ``` 此時第一班電梯肯定就是這些合法的集合 (和$\leq x$) 的其中一個。 那下一班呢? ---- 對於 $(0011)_2$ 如果下一班 $1$ 號上電梯了，就變成 $(0111)_2$ 此時狀態的意義為，哪些人已經上了電梯，此時我們想知道的 $dp[(0111)_2]$ 就是，當這些人都搭上電梯後，的最小班次數。 ---- 觀察一下，對於 $(0011)_2$、$(0101)_2$ 分別多 $1$、$2$ 號搭，都會把狀態送到 $(0111)_2$ 並且這兩個狀態他們都會使班次 + 1 ($1$、$2$ 都分別擠不上第一班)。 那此時對後面的其他狀態而言 (ex. $(1111)_2$)，這個 $(0111)_2$ 當然是保留當下最少搭乘電梯次數的越好，那當次數一樣時，電梯內剩越多空間越好，依照上面的例子，在第二班中 $1$ 號上電梯空間剩 2， $2$ 號上第二班電梯空間剩 4 ，所以留 $(0101)_2 \rightarrow (0111)_2$ 這個轉移。 ---- 這樣就能轉移了，對於每個已上電梯的集合，我們都留最小電梯次數和目前最小電梯負重。 ```cpp= #define pp pair<int,int> #define ff first #define ss second const int MXN = 2e5+5,MOD = 1e9+7; pp dp[(1<<20)]; void solve(){ int n,x; cin >> n >> x; vector<int> w(n); cin >> w; //初始化: 最多搭 n 次，所以開 n+1 當 inf for(int s = 0; s < (1<<n);++s) dp[s].ff = n+1; dp[0].ss = x, dp[0].ff = 0; //沒人上電梯 讓 0 號電梯目前負重是 x 這樣下一個人上電梯一定會搭到第一班 for(int s = 1; s < (1<<n);++s){ //窮舉全部狀態 for(int i = 0; i < n;++i){ //搭第 i 個人上去 if(!(s & (1 << i))) continue; //如果第 i 個沒搭過，跳過 int pv = s ^ (1 << i); // i 沒搭的狀態 auto [a,b] = dp[pv]; if(b + w[i] > x) b = w[i],++a; // i 搭不上去前一班，多一班 else b += w[i]; //搭的上去 if(a < dp[s].ff) dp[s] = pp{a,b}; //次數少先取 else if(a == dp[s].ff) dp[s].ss = min(dp[s].ss,b); //次數一樣，取最小的負重 } } cout << dp[(1<<n)-1].ff << '\n'; } ``` for 迴圈從小到大，是因為當 $s \subseteq S$ 時， $s \leq S$ ，所以對任意集合它的子集都能夠先被窮舉到。 ---- 一個特別的觀察，你會發現這題用排隊來看時，我們只要窮舉 $n$ 個人的排列 (也就是 $n!$ 種)，然後再每次都載盡量多的人上去 (Greedy)，也能找到解，只不過複雜度會是 $O(n*n!)$，但透過 bitmask dp 能壓到 $O(n*2^n)$ ，就我自己遇到的，很多排列會爆開的題目，都能 bitmask 壓掉。 ---- 繼特別的觀察，再一個例題 ### Hamiltonian Path 一張圖，問你有沒有辦法走過所有點，但每個點都只經過剛好一次  $n$ 個點，$n\leq 20$ ---- 暴力: $n!$ 窮舉所有排列 (點走的順序)，然後去檢查這個順序能不能剛好都只經過所有點一次 $O(n)$， 全部 $O(n*n!)$ ，這複雜度真眼熟。 ---- bitmask: bitmask $S$ 紀錄當前走過哪些點了，由於我們需要知道誰走到誰，所以還要多記 走完 $S$ 這些點後的最後一個點。 $dp[S][i] = 0 \lor 1$ 走過，$S$ 內所有點後以 $i$ 點為最後一個點，是否有合法的路。 那這樣其實就能直接轉移了 ---- 你會發現，如果有 $i \rightarrow j$ 這條邊，那 $dp[S \ \cup \ \{j\}][j] \ or= \ dp[S][i]$ 就這樣。 ---- Code: ```cpp= for(int i = 0; i < n;++i) dp[(1<<i)][i] = true; // 初始化 for(int s = 1; s < (1<<n);++s){ for(int j = 0; j < n;++j){ if(s&(1<<j)) continue; // s 還不能經過 j for(int i = 0; i < n;++i){ if(!(s&(1<<i))) continue; // s 必須得經過 i if(edge[i][j]){ //有 i -> j 的邊 dp[s | (1<<j)][j] |= dp[s][i]; } } } } bool ans = false; for(int i = 0; i < n;++i) ans |= dp[(1<<n)-1][i]; ``` 複雜度 $O(n^2*2^n)$ ---- TSP: 旅行推銷商問題，其實就是帶權重的漢米爾頓路徑問題，小改code就好。 --- ## SOS DP ### [模板](https://github.com/asd7766zxc/Miaotomata_CodeBook/blob/main/dp/sos_dp.cpp) Sum over subset (SOS) 目標就是在解決以下問題，其中 $A$ 是一個對於所有集合給定的函數。 $F[S]=\sum_{x\subseteq S}{A[x]}$ ---- 舉個例子 ```cpp= A[001] = 10 A[010] = 3 A[101] = 4 F[101] = A[101] + A[001] = 10 + 4 = 14 ``` ---- 暴力做一下 假設我們能夠窮舉對於給定的集合 $S$ 的所有子集 $x$ ， 那我們就能在 $O(3^n)$ 時間下搞定， 其中 $n$ 是集合大小，或稱 bitmask 的長度。 好所以這 $O(3^n)$ 怎麼來的? ---- 一樣，在給定一個 $S$ 的情況下，我們知道它的 bitmask 表示會有一些地方是 $0$ 一些地方是 $1$。 像這樣 $S=(10110)_2$ 那他的子集 $x$ 其實就是 $S$ 是 $0$ 的地方一定為 $0$ 但剩下的隨便(可為 $0$ 或 $1$)。 所以 $(10010)_2 \in S$ 但 $(11000)_2$ 不是 $S$ 的子集。 ---- 所以對於一個 $S$ 而言，它的子集個數就是 $2^{( \ S \ 的 \ 1 \ 的個數)}$。 接下來考慮全部的 $S$ ，對於 $\ 1 \ 的個數是 \ k \ 的 \ S \ 而言會 \ {{n}\choose{k}} \ 這麼多$ $然後每個再窮舉，所以 {{n}\choose{k}}2^k$ 根據二項式定理 ${{n}\choose{0}}2^0 + {{n}\choose{1}}2^1 + \cdots + {{n}\choose{n}}2^n = (1+2)^n = 3^n$ ---- 說這麼多，所以 how to 窮舉? 對於 $S=(001011)_2$ 我們可以只考慮 $1$ 的地方對吧， 所以把他看成這樣 $S=(XX1X11)_2$ 然後開始往下數， $(XX1X11)_2$ $(XX0X11)_2$ $(XX1X01)_2$ $(XX0X01)_2$ $(XX1X10)_2$ $(XX0X10)_2$ $(XX1X00)_2$ $(XX0X00)_2$ 這樣就能窮舉完 $S$ 的子集。 ---- 所以我們只要每次都把 左起第一個 $1$ 變成 $0$ 然後把這個 $1$ 往左所有的 $0$ 都變成 $1$ 你會發現 $S-1 = (110011)_2$ ， 所以對原 mask 減 $1$ 就能辦到上述效果，再來把不該是 $1$ 的 bit 全部再翻成 $0$ 就搞定了。 ---- 窮舉子集: ```cpp= for(int mask = S; mask; mask = (mask-1) & S){ // S 包含 mask } ``` 注意空集合也就是 $mask = 0$ 要另外做，不然會壞 : 因為 (-1 & S) 會跑回去一個正數 ---- 所以暴力做的 SOS 就會長 ```cpp= for(int S = 0; S < (1LL<<S); ++S){ for(int mask = S; mask; mask = (mask-1) & S){ F[S] += A[mask]; } F[S] += A[0]; } ``` 複雜度 $O(3^n)$ ---- 但通常題目會給到 $n\leq20$ 左右，此時 $3^n=3.4e9$ 老慢了。 這時，我們就要優化一下，接下來的內容會有點抽象。 ---- 我們先放code: ```cpp= // 求子集和 或超集和 -> !(mask & (1 << i)) for(int i = 0; i<(1<<N); ++i) F[i] = A[i]; //預處理 狀態權重 for(int i = 0;i < N; ++i){ for (int s = 0; s < (1<<N) ; ++s){ if (s & (1 << i)){ F[s] += F[s ^ (1 << i)]; } } } ``` 這就是 SOS dp 的全貌 複雜度 $O(n * 2^n)$ ---- ### SOS dp = 前綴和 接下來的觀點是由這裡來的 [SOS dp insights](https://codeforces.com/blog/entry/105247) 有興趣可以翻翻。 ---- Recall: 如果 $x$ 是 $S$ 的子集，則$S$ 是 $0$ 的地方一定為 $0$ 但剩下的隨便(可為 $0$ 或 $1$)。 換句話說，對於每一維(每一個同位置的bit)而言，都要 $\leq$ $S$ 的每一維。 也就是說，假設我們把 $S$ 跟原點做一個每個邊都跟軸平行的矩形 (假設在二維平面上)，那落在這個平面內的點都會是 $S$ 的子集。 ---- ex: 為了方便演示，我把base拉成10進位  $S=(23)_{10}$ $D=(12)_{10}$ $E=(01)_{10}$ $I=(10)_{10}$ 照定義，$S$ 包含了 $D、E、I$，且根據這張圖，它們也確實都落在這個矩形內。 此時如果我想求 $F[S] = A[D] + A[E] + A[I]$ 那 $F$ 就會是一個二維前綴和。 ---- 在了解(相信)，他是前綴和後，我們接下來要解決的問題變成，如何做這麼高維($dim=n\leq20$)的前綴和? ---- 一維前綴和都會吧 ```cpp= // 初始讓每個單點都是一個值 for(int x = 0; x < n;++x) F[x] = A[x]; for(int x = 1; x < n;++x) F[x] += F[x-1]; //這樣等價我們把點給累加起來 ``` ---- 那二維呢?  我們會一維那我們先做一維的 (固定 $y$) ```cpp= #define rep(i,j,n) for(int i = j; i < n;++i) // 初始讓每個單點都是一個值 rep(x,0,n) rep(y,0,n) F[x][y] = A[x][y]; rep(y,0,n){ for(int x = 1; x < n;++x) F[x][y] += F[x-1][y]; } //把每個 y 分別和成一條前綴和 ``` ---- 加完就長這樣每一條都是對 $x$ 的前綴和  這時候求二維前綴和就很好求了，你會發現就是把這一條條的前綴和(線)，疊成一個矩型(面)。 ---- ```cpp= #define rep(i,j,n) for(int i = j; i < n;++i) // 初始讓每個單點都是一個值 rep(x,0,n) rep(y,0,n) F[x][y] = A[x][y]; for(int y = 0; y < n;++y){ //把每個 y 分別和成一條前綴和 for(int x = 1; x < n;++x){ F[x][y] += F[x-1][y]; } } for(int y = 1; y < n;++y){ //把每條都疊起來 for(int x = 0; x < n;++x){ F[x][y] += F[x][y-1]; } } ``` ---- 你會發現 第一輪是 $F[x][y] += F[x-1][y]$ 第二輪是 $F[x][y] += F[x][y-1]$ 也就是說對應的每一維他會由這維的 $-1$ 來。 如果不信，我現在畫一個三維的 ---- $F[x][y][z] += F[x-1][y][z]$ <img src="https://hackmd.io/_uploads/S1ssW8Ilgg.png" width="70%"/> 先對 $x$ 做前綴和就會變成垂直 $x=0$ 這個平面的那堆線(如圖黑色的直線)。 依此類推再來就是面 (對 $y$ 做)，跟 6 面體 (對 $z$ 做)。 ---- 好，所以總得來說只要我們分別對每一個照某個順序做前綴和，就能做完全部的前綴和。 由於mask的每一維只有兩個數字 ($0 \lor 1$)，所以只有$1$的那些人才需要做 $[x] = [x-1]$ 這種事。 ```cpp= for(int i = 0; i<(1<<N); ++i) F[i] = A[i]; //預處理 狀態權重 //也就是前面前綴和的單點值 for(int i = 0;i < N; ++i){ //窮舉目前在哪一維 (x,y,z ...) //同前面，窮舉所有點 for (int s = 0; s < (1<<N) ; ++s){ //對於 x 包含於 S -> x <= S (值的部分) 所以數值小的先做 if (s & (1 << i)){ // 這個就是該維是 1 的意思 F[s] += F[s ^ (1 << i)]; // [x] = [x-1] } } } ``` ps: 其實你只要會用就好 ---- [例題](https://vjudge.net/contest/715073#problem/G): 這題是 virtual 題(gym 105633K)。 $n$ 個時間點， $m$ 個人， $a_{ij}$ = $Y \ or \ N$ 表示編號為 $j$ 的人能不能在第 $i$ 個時間點開會。 你要找兩個時間點，使得這兩個時間點聯集起來這 $m$ 個人，每個人至少都有開到一次會。 如果有多個這樣的時間點對，輸出兩個時間點交集最大的，如果還有重複，輸出兩個時間點越早越好。 - $2 \leq n \leq 2*10^5$ - $2 \leq m \leq 20$ ---- 暴力一下: 先 $O(n^2)$ 枚舉這樣的 pair，那你會發現就是要找任兩行 $or$ 起來是 $(1<<m)-1$ 的，和 $and$ 起來 $1$的個數是最多的 (假設 $Y=1,N=0$)。 ```cpp= for(int i = 0;...){ for(int j = 0;...) } ``` 那有沒有辦法把 $j$ 那圈壓掉? ---- SOS: 你會發現 SOS dp 的 $F[S]$ 其中包含了所有 $S$ 包含的和，那對於 $S$ 的子集而言，$S$ 是 $0$ 的地方子集也一定是 $0$。 那當我們今天在窮舉的時候，假設窮舉到 $(011001)_2$ ，那另一個與他配對的，就必須在這個時間點 $0$ 的地方是 $1$ ，也就是長 $(1XX11X)_2$ 這樣他們 $or$ 起來必定是 $(1<<m)-1$， 所以這樣第二維就能壓掉了，只要我們把 $Y = 0,N = 1$ 然後塞進 SOS 裡面，就能找到這些人。 ---- 但這樣要怎麼找交集最大的? 其實就是留 $1$ 的個數最多的在 SOS 裡，因為外面那圈再查找的時候，自己的 bitmask 上的 $0$ 找到的都會是 $1$ 此時交集的 $1$ 個數就會是 F[x].(1's) - 自己的0's。 對於SOS而言，自己的0's就是定值，故F[x].(1's) 越大越好。 剩下時間也是同理，變一下就好。 ---- Code: ```cpp= vector<pp> F((1LL<<m)); for(int i = 0; i < (1<<m);++i) F[i] = {A[i],B[i]}; auto work = [&](pp &p,pp c){ if(c.ss == n+5) return; if(p.ff < c.ff) p = c; if(p.ff == c.ff) chmin(p.ss,c.ss); }; for(int i = 0; i < m;++i){ for(int s = 0; s < (1<<m);++s){ if(s & (1<<i)){ work(F[s],F[s^(1<<i)]); } } } pp ans(n+5,n+5); int m1 = -1; for(int i = 0; i < n;++i){ int x = ((1<<m)-1) - P[i]; int cx = m - __builtin_popcount(x); auto [p1,p2] = F[x]; if(p2 == i || p2 == n+5) continue; debug(p2); int a = i; int b = p2; if(a > b) swap(a,b); int dx = p1-cx; debug(a,b,dx); if(dx > m1){ ans = pp{a,b}; m1 = dx; }else if(dx == m1){ if(ans.ff > a) ans = pp{a,b}; if(ans.ff == a) chmin(ans.ss,b); } } if(m1 >= 0){ cout << ans.ff +1 << ' ' << ans.ss + 1 << '\n'; }else{ cout << "No\n"; } ``` 所以 SOS dp 通常要變一下。 --- [題單](https://vjudge.net/contest/715073)