<style> .reveal .slides { text-align: left; font-size:35px } </style> ## DP&DP&DP ---- * DP * 狀態壓縮 * SOS DP * 矩陣快速冪 --- ## 什麼是狀態壓縮? 其實狀態壓縮大家應該都會，只是不知道它就是狀態壓縮，狀態壓縮簡而言之就是簡單的使用最小狀態去表示每個需要的狀態，使得可以表達的狀態變多。 最簡單且常見的狀態壓縮就是使用二進制的 $0/1$ 數組去表示一個東西取或不取，當然如果你有大於兩種狀態，你也可以用三進制或是更多去表示。 也就是把一個狀態轉化成一個數字(將一行的狀態壓成一個數字)，然後使用位運算去進行處理。 ---- ## 狀態壓縮的使用時機 1. 需要保存狀態，像是dp就是很好的例子，像是棋盤放或不放，硬幣正面或反面，物品取或不取，以上都是二進制的例子。 2. 需要縮小儲存數據的空間以及提高處理效率的時候 ---- ## 狀壓DP 一般的狀壓就是將一行的狀態壓成一個數，這個數的二進制就是這一行的狀態。由於使用二進制數來保存被壓縮的狀態，所以再處理時就要使用到位運算。 ---- 那在這邊舉例一些常用的操作 : |作用|具體用法| |-----------|------| | 去掉最後一位 | $x>>1$ | |在最後增加一個0| $x<<1$ | |在最後增加一個1| $x<<1\|1$ | |把第k位變成1| $x\|(1<<(k-1))$ | |把第k位變成0| $x\& \sim (1<<(k-1))$ | |取第k位| $x>>(k-1)\&1$ | ---- ## [例題](https://www.luogu.com.cn/problem/P1896) 直接舉例題看抽象的狀態壓縮是什麼 題意 : 再$N*N$的棋盤裡面放$K$個國王，求最多有幾種方案數。 $N，K （ 1 \leq N \leq 9, 0 \leq K \leq N * N）$ 解法 : 定義 $dp[i][j][k]$ 為只考慮前 $i$ 行時，有且只有 $k$ 個國王，且第 $i$ 行國王的編號為 $j$，而其中用到狀態壓縮的地方就是第 $i$ 的狀態 $j$ 是用二進制代表的。  ---- 為了滿足以上的dp式，那我們剛開始要預處裡兩個數組，分別是$sit$和$now$，其中$sit$數組指的是所有的組合，而$now$數組指的是在這個狀態裡面有幾個國王(有幾個1) $sit(j)=100101_{(2)}=37, now(j)=3$ 所以我們就要在剛開始先dfs枚舉每一個滿的數組 0 ~ 1 ```cpp void dfs(int he,int sum,int node){ if(node>=n){ sit[++cnt]=he; now[cnt]=sum; return;//新建一個狀態 } dfs(he,sum,node+1);//現在這格不放國王，所以下一格是node+1 dfs(he+(1<<node),sum+1,node+2);//現在這格放國王，所以下一格是node+2 } int main(){dfs(0,0,0);} ``` ---- 再來就是初始化，對於每一個格子一定會有一個最爛的方案就是它自己擺，其他全部不擺國王，因此初始化為 : ```cpp for (int j=1;j<=cnt;j++) f[1][j][now[j]]=1; ``` 那既然這樣就十分好理解轉移式應該要怎麼轉移了，那就很明顯是要枚舉 $i,j,k$然後 ```cpp for(int s=king;s>=now[j];s--) dp[i][j][s]+=dp[i-1][k][s-now[j]]; //now為這個狀態下這一行放的國王數量 ``` 枚舉放滿每個國王 (s=king) 一直到最少這一行有放的最大值(s>=now[j]) ---- 那記得在枚舉的時候有某些情況是需要忽略的，那接下來是實作時間。 ---- ## [例題2](https://www.luogu.com.cn/problem/P1879) 題意 : 給出 $n*m$ 的格子，其中若格子為0則不能放，只能放在棋格為1的地方，以及另外一項限制為不能放相鄰的棋子，詢問一共有幾種放置方法。$(mod 1e8)$ $(1 \leq N,M \leq 12)$ 解法 : 會發現它跟剛剛第一題幾乎一樣，其實也確實都是一樣的想法，完全可以直接把棋格當成二進制的數字，這樣子僅用一個數字就可以表達一行的狀態，然後定義 $dp[i][j]$ 為前 $i$ 行，且第 $i$ 行的方案數為 $j$ 的方案總數 ---- 那跟上一題一樣，第一步就是要預先處理每一行的狀態壓縮 ```cpp for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>x,sta[i]=(sta[i]<<1)+x; for(int i=1;i<=(1<<m)-1;i++) if(!(i&(i<<1))&&!(i&(i>>1))) is_legal[i]=1; //初始化是否合法，也就是相鄰的格子沒有放置 ``` ---- 那再來就是dp轉移式，初始化 $dp[0][0]=1$(合法方案)接下來循環每一行，然後去枚舉這行的每個方案，若是當前方案合法且可放置就可以針對該方案去枚舉。 ```cpp for(int i=1;i<=n;i++){ //循環每一行 for(int j=0;j<=(1>>m)-1;j++){ //枚舉那一行的每一個方案 if(is_legal[j]&&((j&sta[i])==j)) //若當前合法且與剛開始的status一樣 for(int k=0;k<=(1>>m)-1;k++) //則枚舉這個方案 if(!(j&k)) //若k方案和上一個方案j可以同時存在，則把此方案加入答案 dp[i][j]=(dp[i][j]+dp[i-1][k])%mod; } } ``` ---- [例題三](https://atcoder.jp/contests/dp/tasks/dp_o?lang=en) 題意: 給出一個 $n\times n$ 的矩陣，其中若 $a_{ij}$為1，則代表 $X_i$ 和 $Y_j$ 可以配對，反之。 求有幾種讓所有的 $X$ $Y$ 皆有配對的方法。 ---- 那狀態壓縮，一樣需要先進行預處裡。 ```cpp for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin >> a[i][j]; b[i]+=((1&a[i][j])<<j); //處理狀態 } } ``` ---- 然後初始化，你會發現DP定義應為 $dp[i][mask]$ 第$i$個人選取狀態已為 $mask$的方法數，其中 $mask$ 的1的數量由於題目特性，一定為 $i$ 個 所以每一個 $dp[i][mask]$ 就是從 $dp[i-1][每一個合法的k]$ 轉移過來 ```cpp for(int j=1; j <=n;j++){ if (!a[i][j]) continue; x=(1<<j); for(int k=1;k<(1<<n);k++){ //枚舉每一個合法的狀態 if((x&k)!= 0||!dp[i-1][k]) continue; //若不合法，或是前一個人根本沒辦法這樣配對 dp[i][x|k]+=dp[i-1][k],dp[i][x|k]%=mod; } } ``` ---- [例題四](https://cses.fi/problemset/task/1653) 題意:講義題，有$N(1\leq N \leq 20)$個人，坐電梯，電梯負重為$W$，詢問需要幾次才可以把所有人載完。 那剛開始可能會想要貪心之類的，然後你就錯了。 你可能會想要背包之類的，然後發現負重是 $10^9$ 你又錯了。 所以這題的思路需要在$N \leq 20$ 出發。 ---- 那我們的DP就可以開 $(1<<N)$ 代表每個人已經坐上去的狀態，存的內容則是需要幾趟電梯，以及可以多存當前最新的這趟還有多少重量可以給予其他人乘坐。 所以對於任意一個 $(x|(1<<i))!=x$ 的dp轉移式，就還必須判斷他的重量，也就是 $dp[x].second>=weight[x|(1<<i)]$，那必須符合才可以轉移，不符合的話則需要轉移到 $dp[x+1]$ ---- 這題是作業題，而且是相對非常簡單的作業題，所以不附上代碼，利用上面的講解一定寫得出來。 --- ## SOS-DP ## [模板](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/others/SOS_dp.cpp) SOS的全名為Sum over Subsets，也就是說這種DP方式是用來優化子集和的問題 可以拿來優化以下問題的解 : $f [mask] = \sum_{x\&mask=x} a_x$ 那如果他的 $N$很小，那當然可以用最簡單的暴力方式去求解 ```cpp for (int mask = 0; mask < (1 << N); mask++) for (int i = 0; i <= mask; i++) if ((mask & i) == i) F[mask] += A[i]; ``` 此時的時間複雜度為 $O(4^N)$ ---- 然後你就會發現這樣非常沒有效率，觀察一下if的式子 $((mask \& i) == i)$ 就會輕鬆地發現，原本的做法枚舉到太多沒有用的子集，他第一個符合條件的頂就是 $i==mask$，而每次要達成if述句的條件就是需要讓 $i$ 的下一個為$1$的bit變成$0$，於是就可以得出這樣的簡化 ```cpp for (int mask = 0; mask < (1 << N); mask++) for (int i = mask; 1 ; i = ((i - 1) & mask)){ F[mask] += A[i]; if(i == 0) break; } ``` 而此時的時間複雜度為 $O(3^N)$ -- 可以使用二項式定理證明。 ---- 那到目前為止，還有哪裡可以優化呢? 你會發現，若 $i$ 當前計算的bit是 $0$ ，則完全不需要考慮他，而如果這位是 $1$ 的話，就會有許多子集，也會發現下一個要去枚舉的就是 mask xor $2^i$，所以你就會發現，會得出以下式子  於是就可以先預處裡所有的dp，然後就可以快速地去枚舉所有之後為 $1$的子集 ---- ```cpp for (int mask = 0; mask < (1 << N); mask++) //預處理 dp[mask][0] = A[mask]; for (int mask = 0; mask < (1 << N); mask++) for (int i = 1; i <= N; i++){ if (mask & (1 << (i - 1))) dp[mask][i] = dp[mask][i - 1] + dp[mask ^ (1 << (i - 1))][i - 1]; else dp[mask][i] = dp[mask][i - 1]; //根據上圖得出的轉移式 } F[mask] = dp[mask][N]; ``` 這時的時間複雜度壓縮為 $O(N * 2^N)$ ---- 然後就可以發現，dp數組只會用到 $dp[x][i]$ 和 $dp[x][i-1]$ ，因此根據之前所教到的，我們可以輕易的使用滾動數組優化，然後就會變成 : ```cpp for(int i = 0; i<(1<<N); ++i) F[i] = A[i]; //預處理 for(int i = 0;i < N; ++i) for (int mask = (1<<N)-1; mask >= 0 ; mask--) if (mask & (1 << i)) F[mask] += F[mask ^ (1 << i)]; ``` *這就是最重要的結論 ---- ## 結論 想辦法把題目推成這個樣式 $f [mask] = \sum_{x\&mask=x} a_x$ 這個問題，把該給的給進去 ```cpp for(int i = 0; i<(1<<N); ++i) F[i] = A[i]; //預處理 for(int i = 0;i < N; ++i) for (int mask = (1<<N)-1; mask >= 0 ; mask--) if (mask & (1 << i)) F[mask] += F[mask ^ (1 << i)]; ``` 這個帶進去 over --- # 矩陣快速冪 ---- 先複習一下矩陣乘法的程式碼 矩陣乘法程式碼： ```cpp= for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ for(int k = 0; k < n; k++){ ret[i][j] += a[i][k] * b[k][j]; } } } ``` ---- 例題： 環塗色 題序： 給兩個整數 $n$、$\lambda$， $\lambda$ 是有多少種顏色，n 是指有幾個頂點圍成的環，問你有幾種塗色方式可以讓環上連在一起的頂點兩兩顏色都不同 範圍：n、$\lambda \le 10^9$  n = 3, $\lambda$ = 3 以上為 6 種塗色方法 (1,2,3) (1,3,2) (2,1,3) (2,3,1) (3,1,2) (3,2,1) <!--  --> <!-- https://icpc2022.ntub.edu.tw/wp-content/uploads/2022/11/ICPC2022-main.pdf --> ---- 先用數學想法思考最簡單的結論 可以發現如果直接推的話，會長左下這樣，但是因為這樣很明顯無法知道最後一個的顏色是什麼，因此這個推法是錯的。  ---- 如果要正確推出多邊形有幾種塗色的方式，我們需要知道最後一個跟第一個不一樣的塗法有幾種，因此我們需要記錄每個節點跟第一個一樣及跟第一個不一樣的塗法 $color[i][0]$ 是指第 $i$ 個節點與第一個不一樣顏色的話有幾種塗法 $color[i][1]$ 是指第 $i$ 個節點與第一個一樣顏色的話有幾種塗法 ---- 轉移就會變成以下這樣 $color[i][0] = color[i - 1][0] * (\lambda - 2) + color[i - 1][1] * (\lambda - 1)$ $color[i][1] = color[i - 1][0]$ 而初始值是 $color[0][0] = 0$ $color[0][1] = \lambda (在第一個的時候顏色會跟自己一樣，因此是 \lambda)$ ---- 但這樣還沒有做完，因為他的 $k$ 的範圍最多到 $10^9$，除了沒辦法開那麼大的陣列以外，時間也不足以跑完 $10^9$，這時候就需要矩陣快速冪加速了。 ---- 推導過程： ${\begin{bmatrix} \lambda - 2 &\lambda - 1\\1&0 \end{bmatrix}}\quad \times \quad \begin{bmatrix} \text{color[0][0]}\\\text{color[0][1]}\end{bmatrix}$ <!--  --> ---- 通過以上的推導，我們就可以對求出的矩陣做快速冪，在 $O(log_2N)$ 的時間找出我們要的多邊形塗色的答案了，也就是 color[n - 1][0] (第 $n$ 個跟第一個顏色不同的塗法)。 ---- ## 2022 ICPC  題意 : 給你三個數字 $n$ , $k$ , $\lambda$ 分別是中間的多邊形邊數，外擴的四邊形層數，顏色種數，詢問有幾種塗色方案(隔壁不能重複)。 ---- 知道了環內的選擇方法後外面就很簡單了，外面第一層就是 $k_{value} = \frac{1}{\lambda-1}*(\lambda-1)+\frac{\lambda-2}{\lambda-1}*(\lambda-2)$ 然後 $(k-1)*n*k_{value}*color[n-1][0]$ 就會是答案。 ---