<style> .reveal .slides { text-align: left; font-size:35px } </style> ## DP與數學 ---- * DP * 狀態壓縮 * SOS DP * 數學 * 歐拉 * 莫比烏斯反演 * burnside lemma * Pólya lemma --- ## 狀態壓縮 ---- ## 什麼是狀態壓縮? 其實狀態壓縮大家應該都會，只是不知道它就是狀態壓縮，狀態壓縮簡而言之就是簡單的使用最小狀態去表示每個需要的狀態，使得可以表達的狀態變多。 最簡單且常見的狀態壓縮就是使用二進制的 $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; } } ``` --- ## 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 ---- ## 例題 題意 : 給你 $n$ 個數字$(1 \leq N,a_i \leq 10^6)$，求有幾對pair $(a_i \& a_j)==0$ 題解 : 那首先先分析pair若要&起來等於零，代表他們沒有任何相同的位元是 $1$ ，所以最多就是有$log_2$ $max_{a_i}$個位元 我們只要把每個數字的 $x$ 疊起來計算，就很明確就是求 $f [mask] = \sum_{x\&mask=x} a_x$ 這樣表示的話，其中 $f[i]$ 是 $mask$ 子集的和。 而其中pair數就是 $mask$ 補集的 $f$ 值 ---- ```cpp const int maxn = 1<<20; //1e6 int t,n,x,ans=0; int a[maxn<<1],f[maxn<<1],mx=(1<<20); int main(){ cin >> n; for(int i=1;i<=n;i++) cin>>x,a[x]++; for(int i=0;i<mx;i++) f[i] = a[i]; for(int i=0;i<20;i++) for(int j=mx-1;j>=0;j--) if(j&(1<<i)) f[j]+=f[j^(1<<i)]; for(int i=0;i<=1000000;i++) ans+=1ll*a[i]*f[(mx-1)^i],a[i]=0; cout<<ans; } ``` 其複雜度為 $O(N*2^N)$ 而 $N$ 為$log_2$ $max_{a_i}$ --- ## 歐拉函數 ---- ## 定義 $\phi (x)$ 為小於等於 $x$ 且和 $x$ 互質的數字個數，也就是 $\phi (1)=1$ 若 $x$ 為質數 則 $\phi (x)=x-1$ ---- ## 性質 1. 歐拉函數為積性函數 \*積性函數是指 若有 $gcd(a,b)=1$ 那 $\phi (a*b)=\phi(a)*\phi(b)$ 其中 若 $x$為奇數時，$\phi(2x)=\phi(x)$ 2. $n=\sum_{d \mid n} \phi(d)$ 3. 若$n=p^k$ ，且 $p$ 是質數的話，那 $\phi(n)=p^k-p^{k-1}$ 4. 由算術基本定理可知 $\phi(n)=n*\prod_{i=1}^s \frac {p_i-1}{p_i}$ 由第四點求出的通式$\phi(n)=x*\prod_{i=1}^n (1-\frac 1{p_i}))$ ---- 怎麼求歐拉函數 ```cpp int Euler(int n){ int now = n; for (int i = 2; i * i <= n; i++) if (n % i == 0){ now = now - now / i; while (n % i == 0) n = n / i; } if (n > 1) now = now - now / n; return now; } ``` ---- 那當然上面那個看起來很慢，所以我們會有更快的 : ```cpp int prime[10010], phi[10010]; bool v[10010]; void quick_euler(){ int cnt = 0; for(int i = 2; i <= N; ++i){ if(!v[i]) prime[++cnt] = i, phi[i] = i - 1; // 若 i 是質數，所以 φ(i) = i - 1 for(int j = 1; i * prime[j] <= N && j <= cnt; ++j){ v[i * prime[j]] = 1; if(i % prime[j] == 0){ phi[i * prime[j]] = phi[i] * prime[j]; break; } else phi[i * prime[j]] = phi[i] * (prime[j] - 1); } } } ``` --- ## 莫比烏斯反演 ---- ## [模板](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/math/primes.cpp) 莫比烏斯反演是數論裡較為重要的一塊，通常提到數論會提到的三大魔頭之一(其餘兩個是EXGCD和中國餘式)。 而在學習莫比烏斯反演之前需要學習兩個前備知識(狄利克雷摺積以及積性函數)，但是要講的話可能要講10幾個小時，反正沒有很重要，大概一年會遇到一題。 ---- ## 用法 若有函數 $f(n) = \sum_{d\mid n}g(d)$ ，則 $g(n) = \sum_{d\mid n} \mu(d)f(\frac nd)$ 預先處理 $\mu(n)$ 的時間複雜度是 $O(n)$ 看起來很簡單，但又不知道應該怎麼用，所以就應該直接背結論當公式用然後直接做例題。 若對前導知識及過程有興趣，可以去搜尋 狄利克雷摺積 ---- ## 直接跳到結論 以下是常見的用法 1. LCM(a,b) 直接等於 $\frac {ab}{gcd(a,b)}$ (常識) 2. 當 $a<b$ , $gcd(a,b)=gcd(b-a,b)$ (常識) 3. $\sum\sum gcd(a,b)可轉為 \sum_{d}\sum\sum [gcd(a,b)=1]$ 4. $[gcd(a,b)=1]$ 可轉換為莫比烏斯函數 $\sum_{d\mid gcd(a,b)} \mu(d)$ 5. $\sum$ 是具有交換律的，可以透過交換順序去壓縮複雜度 6. 原本要枚舉因數的時間複雜度可以透過直接加法省略 : $\sum_{i=1}^n\sum_{j=1}^m\sum_{x\mid i}\sum_{y\mid j} 1$ 透過觀察因數，可以發現轉換成這個是等價的 : $\sum_{x=1}^n\sum_{y=1}^m \lfloor \frac nx \rfloor \lfloor \frac my \rfloor$ ---- ## [例題](https://cses.fi/problemset/task/2417) 首先是一道CSES上的裸題，題意為詢問長度為 $N$ $(1 \leq N \leq 1e6)$陣列中有幾對互質的pair 首先最簡單的枚舉取GCD是否等於 $1$，那複雜度就是 $O(N^2)$ ```cpp for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) ans+=(__gcd(v[i],v[j])==1)?1:0; ``` 那很簡單就可以寫出這個式子 : $\sum_{i=1}^N \sum_{j=1}^N[gcd(a_i,a_j)=1]$ ---- 知道這個式子之後，那根據這個結論 $f(n) = \sum_{d\mid n}g(d)$ ，則 $g(n) = \sum_{d\mid n} \mu(d)f(\frac nd)$ 我們就可以把$\sum_{i=1}^N \sum_{j=1}^N[gcd(a_i,a_j)=1]$ 裡面的 $[gcd(a_i,a_j)=1]$ 換成 $\sum_{d\mid gcd(a_i,a_j)}\mu(d)$ 那同時 $d\mid gcd(a_i,a_j)$ 也等價於 $d\mid a_i,d\mid a_j$ 所以原式會變成$\sum_{i=1}^N \sum_{j=1}^N\sum_{d\mid a_i,d\mid a_j}\mu(d)$ ---- 然後我們只需要簡化前面的這個數學式，也就是 $\sum_{i=1}^N \sum_{j=1}^N\sum_{d\mid a_i,d\mid a_j}$的部分 那很清楚的，若是 $d$的倍數可以預處理的話整個式子會變簡單很多，我們可以透過枚舉去紀錄 $d$的倍數紀錄為 $cnt[d]$ ，所以整個前面的數學式就可以簡化成 : $\sum_{d=1}^N \mu(d)\dbinom{cnt[d]}{2}$ 然後總時間複雜度就會是 預處理的 $O(n) + 算倍數的調和級數 O(nlgn) = O(NlgN)$ ---- ## [例題](https://www.spoj.com/problems/LCMSUM/) 給定 $N$ ，求 $\sum_{i=1}^n lcm(i,n)$ $t \leq 3e5 , n \leq 1e6$ 這題有兩種方式，莫反或者是簡單數論都可以，但最後都會推導到一樣的終點，所以這邊用莫反的推導方法。 ---- ## 莫比烏斯反演分析 原式為 : $\sum_{i=1}^n lcm(i,n)$ 可以先轉為 $\sum_{i=1}^n \frac{i * n}{gcd(i,n)}$ 然後透過結論第三條 : $\sum\sum gcd(a,b)可轉為 \sum_{d}\sum\sum [gcd(a,b)=1]$ 此數學式可展開為 $n \sum_{d \mid n} \sum_{i=1}^n \frac id[gcd(i,n)=d]$ 然後把 $\frac nd$置換掉裡面的 $n$ (因為因數的關係，所以最後推出來會是一樣的) 就會變成$n \sum_{d \mid n} \sum_{i=1}^{\frac nd} \frac id[gcd(i,\frac nd)=d]i$ 然後就會發現，只需要枚舉$gcd(i, \frac nd)$就可以解決這題了，因為他可以轉換成 $n \sum_{d \mid n}\phi (\frac nd) \frac n{2d}$ ---- ## 數論分析 原式為 : $\sum_{i=1}^n lcm(i,n)$，可轉為 $\sum_{i=1}^n \frac{i * n}{gcd(i,n)}$ 同時他可以拆成 $\frac 12\sum_{i=1}^n \frac{i * n}{gcd(i,n)}\sum_{i=n}^1 \frac{i * n}{gcd(i,n)}$ 然後把最後一層 $n$ 分解出來，因為當把 $i=n$代進去時，會等於 $n$ ，所以可以直接分解，結果如下 : $\frac 12\sum_{i=1}^{n-1} \frac{i * n}{gcd(i,n)}\sum_{i=n-1}^1 \frac{i * n}{gcd(i,n)}+n$ 然後又因為 當 $a<b$ , $gcd(a,b)=gcd(b-a,b)$ 所以式可以轉化為 $\frac 12\sum_{i=1}^{n-1} \frac{i * n}{gcd(i,n)}\sum_{i=n-1}^1 \frac{i * n}{gcd(n-i,n)}+n$ 然後就會發現兩個 $\sum$的分母其實是一樣的，所以可以合併，會變成 : $\frac 12\sum_{i=1}^{n-1} \frac{n^2}{gcd(i,n)}+n$ ---- $\frac 12\sum_{i=1}^{n-1} \frac{n^2}{gcd(i,n)}+n$ 這個步驟我們把最後面的 $n$代回前面的求和式 $\frac 12\sum_{i=1}^{n} \frac{n^2}{gcd(i,n)}+ \frac n2$ 到這步之後，答案其實顯而易見了，裡面有倍數關係且可以快速計算的是$gcd(i,n)$ 所以只需要統計 $gcd(i,n)=d$的個數，當 $gcd(i,n)=d$時，$gcd(\frac id, \frac nd)$ 這之後就可以一樣用莫反的推法延伸下去了。 --- ## burnside lemma && Pólya lemma ---- Pólya定理其實就是進一步的burnside引理 那就是再詢問給定的格子，總共有多少種塗色方案 發現大家都直接用例子講，所以我也決定用例子講。 有2\*2的格子，可以選擇要不要塗色，問有幾種塗色方案。  ---- 而其中把旋轉定義為 $g_i$ $g_1 = 旋轉0度$ $g_2 = 旋轉90度$ $g_3 = 旋轉180度$ $g_4 = 旋轉270度$ 而其中我們把 $f(g_i)$ 代表可以旋轉那麼多度，依舊本質不同的方案 ---- $f(g_1) = \{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16\}$ $f(g_2) = \{1,2\}$ $f(g_3) = \{1,2,11,12\}$ $f(g_4) = \{1,2\}$  ---- 根據burnside引理，最終會有多少不同本質的方案 $L$ 呢? $L=(f(g_1)+f(g_2)+f(g_3)+f(g_4))/4$ $=(16+2+4+2)/4=6$ 也就是在那四種置換的前提下，burnside引理下最終會有6種不同本質的塗色方案 ---- 下一個例子 用十種顏色再9宮格填色，詢問有幾種本質不同的塗色方法。  ---- 那一樣有四種置換方式 $g_1 = 旋轉0度$ $g_2 = 旋轉90度$ $g_3 = 旋轉180度$ $g_4 = 旋轉270度$ 那 $g_1$ 的話，當然就是有$10^9$(10種顏色9個格子) 種塗色方案 那 $g_2$ 的話，你會發現上面的九宮格，(1,3,7,9)和(2,4,6,8)分別是循環的一團。所以會發現再 $g_2$ 的方案下，會有三個格子，分別是 (1,3,7,9)和(2,4,6,8)和(5)，所以是有$10^3$種塗色方案 那 $g_3$ 的話，對稱的(1,9)(3,7)(2,8)(4,6)(5)，他們也分別是循環的一團所以是有$10^5$種塗色方案。 那 $g_4$ 的話則跟 $g_2$ 一樣，所以也是 $10^3$ ---- 那麼根據burnside引理，最終會有多少不同本質的方案 $L$ 呢? $L=(f(g_1)+f(g_2)+f(g_3)+f(g_4))/4$ $=(10^9+10^5+10^3+10^3)/4$ 那這樣應該可以發現 polya定理的公式長相如下 : $L = \frac 1{\mid G \mid}[m^{c_1}+m^{c_2}+...m^{c_g}]$ 其中 $L$就是方案數 $G$是置換方式 $m$ 就是有幾種顏色 現在這樣回頭解析剛剛那兩題就很簡單了，接下來就可以應用到實戰中 ---- ## [[例題]](http://acm.hdu.edu.cn/showproblem.php?pid=4633) 題意 : 用 $k$ 種顏色給一個魔術方塊染色，可以染每個面的 $9$ 個小矩形，$12$條邊，$8$個頂點，空間旋轉後一樣的視為相同，問有多少種本質不同的染色方案 以下是立方體的對稱軸 1. 以兩個相對面的中心相連作為對稱軸，旋轉(i)90，(ii)180，(iii)270度，每種有3個。共9種。 2. 以兩個相對邊的中點連線為對稱軸翻轉180度，有6種。 3. 固定兩個相對頂點旋轉(i)120，(ii)240度，共8種。 4. 最後一種就是完全滿的，沒有對稱軸 ---- 然而根據組合數學可以得出以下的結論 | 面 | 邊 | 頂點 | |--|--|--| |(1) (i) (iii)|(2,0,0,13)|(0,0,0,3)|(0,0,0,2)| |(1) (ii)|(2,26,0,0)|(0,6,0,0)|(0,4,0,0)| |(2)|(0,27,0,0)|(2,5,0,0)|(0,4,0,0)| |(3) (i) (ii)|(0,0,18,0)|(0,0,4,0)|(2,0,2,0)| $1,2,3,4$的總和分別是 $38$ $20$ $26$ $74$ 再依照這個去寫波利亞定理就會AC了 --- ## [HW](https://vjudge.net/contest/570322) ## 今天希望大家至少寫出兩題 QQ