<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)
Google Drive
Gist
Clipboard
Sign in with Wallet
