<style> .reveal .slides { text-align: left; font-size:30px; } </style> # pretrain 2 2023 Introduction to Competitive Programming 2022/12/08 ---- * 矩陣快速冪 * 位元運算 * 前綴和與差分 --- ## 矩陣快速冪 ---- ### 矩陣快速冪 與快速冪類似，差別只有快速冪是對數字，而矩陣快速冪是對矩陣做。 ---- ### 例題： 費式數列 $F_0 = 0, F_1 = 1$ $F_n = F_{n-1} + F_{n-2}$ * subtask 1: $n \le 20$ * subtask 2: $n \le 10^5$ * subtask 3: $n \le 10^{18}$ ---- ### subtask 1：$n \le 20$ trivial 直接遞迴即可 ---- 程式碼 ```cpp= int fib(int n) { if(n <= 1) return n; return fib(n-1) + fib(n-2); } ``` ---- 分析： 藉由下圖可以發現，fib 產生出的遞迴樹的節點會比完全二元樹(*)還少，花費的時間會小於 $O(2^n)$ 在$n \le 20$的情況下，時間複雜度會是好的  ---- ### subtask 2：$n \le 10^5$ dp 可以發現直接遞迴的做法會算到很多次重複的值，因此我們可以通過將值記錄下來，之後跑到就不需要重新計算了。 ---- 程式碼 ```cpp= int dp[] = {0}; int fib(int n) { if(n <= 1) return n; if(dp[i]) { return dp[i]; } return dp[n] = fib(n-1) + fib(n-2); } ``` ---- 分析： 可以發現上面每個 dp[i] 都只會計算到一次 複雜度 $O(n)$ ---- ### subtask 3：$n \le 10^{18}$ 矩陣快速冪 將 $F_n = F_{n-1} + F_{n-2}$ 的計算推導成矩陣形式  ---- 套用上一張投影片的結論，我們可以發現，如果可以將左邊的矩陣多乘幾次，再乘上右邊 2 * 1 的矩陣，就可以找出我們要的答案了！ ${\begin{bmatrix} 1&1\\1&0 \end{bmatrix}}^{n-1}\quad \times \quad \begin{bmatrix} f[1]\\f[0] \end{bmatrix}\quad = \quad\begin{bmatrix} f[n]\\f[n-1] \end{bmatrix}\quad$ 大概是像這樣 ---- ### 程式碼： ```cpp= int base[2][2] = { int ans[2][2] = { {1, 1}, {1, 0}, {1, 0} {0, 1} }; }; int mypow(int y){ while(y){ if( y&1 ) { ans = mul(ans, base); } //實作矩陣乘法 base = mul(base, base);//實作矩陣乘法 y >>= 1; } return ans[0][0]; } ``` ---- 矩陣乘法程式碼： ```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]; } } } ``` ---- 分析： 快速冪 $O(lgN)$ 矩陣乘法 $O(矩陣大小^3)$ 複雜度 $O(2^3 lg N)$ ---- 例題： 環塗色 題序： 給兩個整數 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$) ---- 這樣就做完了嗎？ No，他的 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 個跟第一個顏色不同的塗法)。 --- ## 位元運算 ---- ### 位元運算 位元運算是對二進位的 0 和 1 做一些處理，然後會出現一些性質和用途。 ---- 二進位理所當然就只有 true(1) 跟 false(0)，以下是位元運算示範操作 ``` AND運算： OR運算： 0 & 0 0 0 | 0 0 0 & 1 0 0 | 1 1 1 & 0 0 1 | 0 1 1 & 1 1 1 | 1 1 XOR運算(⊕)： NOT運算： 0 ^ 0 0 !0 1 0 ^ 1 1 1 ^ 0 1 !1 0 1 ^ 1 0 ``` ---- ### XOR運算 因為 XOR 太多常用性質，所以特別拿出來講。 先來幾個基本原則（bitwise xor 的符號一樣用 ⊕）： A ⊕ B = B ⊕ A，(A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)，也就是運算順序不影響結果(有交換律和結合律)。 A ⊕ A=0 若 A ⊕ B=C，則 A ⊕ C=B A ⊕ 0 = A ---- ### 補數運算 C++程式裡使用 "~" 來表示，補數運算為逐位元取反 顛倒一個變數的每個位元的 0 和 1 ```= ~0=1 ~1=0 常見用法(位元優化dp 總有一天會遇到) 15 & ~(1 << 1) = 13 //將第2個bit設為0 8 |(1 << 2) = 12 //將第3個bit設為1 ``` ---- ### 左移 右移 運算 C++程式裡使用"<<"與">>"來表示，表示為位元左移(右移)一格 左移時最左邊會補上 0 而右移時最右邊位元會被移除 ```= 9=1001 9<<1 = 10010 = 18 15=1111 15>>1 = 111 = 7 常見用法 (x>>1) 快速除2 以及 (x<<1) 和 (x<<1)|1 左子節點和右子節點 ``` ---- ### 位元性質 if (status) while (status) for ( ; status ; ) 以上的 status 都是非 0 就是 true，也就是裡面都是布林值 所以可以常常看到這種寫法 ```cpp= if(array[x]){ //若array[x]的值非零即會進入"True" cout<<"True"; } else{ //只有再array[x]==0的時候才會進入這邊 cout<<"False"; } while(x){ //當x不是0的時候就不會跳出迴圈 x--; cout<<x<<endl; } ``` ---- 規律性質 例題: [[CPE例題](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/12208.pdf)] 詢問 x~y 中所有的數字轉換成二進制後有幾個 1 而當你把位元攤開來之後 0 : 0 0 0 0 1 : 0 0 0 1 2 : 0 0 1 0 3 : 0 0 1 1 4 : 0 1 0 0 5 : 0 1 0 1 6 : 0 1 1 0 7 : 0 1 1 1 8 : 1 0 0 0 || <span class="spoiler-text"> 每個bit拆開來即可發現規律 </span> || ---- 1 最低的'1'位元 ```cpp= x & -x ``` 根據二的補數，-x 為 ~x + 1。因此在這先將 -x 拆開為 ~x + 1 來討論。 x 中最低位的位元 1 經過 not 運算後，將在 ~x 中變為最低位的位元 0。 因此對 ~x 加上 1 後，最低位的位元 0 重新變為位元 1，且其後的位元都將被設定為 0。 2 檢查冪次 是否為二的冪次 ```cpp= (x & -x) == x ``` 由於若你為二的冪次，則該數字只會有一個位元(也是最高位元) ---- ## 練習 練習 1 --- XOR 練習 ```cpp= x^=y^=x^=y ``` 請問 x,y 各為多少?(用 x 跟 y 表示) ---- 拆開來看即為 ```cpp= x = x ^ y; y = y ^ x; x = x ^ y; ``` 答案為 x 為 y ,y 為 x (相等於 swap ( x , y )) ---- 練習 2 --- 優先級的練習 ```cpp= cout<<(15>>1+2); ``` ---- ```cpp= cout<< ( 15 >> 1 + 2 ); ``` ans : 1 大多數的位元運算子的運算優先級都比較低， 因此此題的計算過程為 1 + 2 = 3 , 15(1111) >> 3 = 1. 所以你不確定優先級的時候最好都要加括號 ---- 練習 3 --- 常用的技巧 ```cpp= if(x & 1) return 1; else return 0; ``` ```cpp= return (x & 1); ``` ---- ```cpp= if(x&1) return 1;//(奇數) else return 0;//(偶數) ``` 判斷 x 的奇偶性 也是常見用法 (比較快) 由於一個數字的位元組成都是 2 的冪次方 因此 $2^n$ 只有在 n==1 的時候會影響到數字的奇偶性， 故只需要判斷最後一個位元 --- ## 前綴和、差分 #### 一維前綴和 序列 $A_1, A_2,...,A_n$ 的長度為i的前綴和記為 $S_i$ 而 $S_0$ =0，可以用來計算區間和。 $\sum\limits_{i = l}^r {A_i = S_r -S_{l-1}}$ 可以簡單理解為前 $i$ 項的和，而求 $l ~ r$ 的區間和自然就是$S_r-S_{l-1}$ ---- #### 二維前綴和 多維前綴和的構造方式與一維相同，主要是求區間和時要利用容斥原理 如何構造 矩陣 sum? $sum_{x,y}=\sum\limits_{i = 1}^x \sum\limits_{j = 1}^y {arr_{i,j}}$ 遞推求sum的過程為(容斥原理): $sum_{i,j} = sum_{i-1,j} + sum_{i,j-1} - sum_{i-1,j-1} + arr_{i,j}$ ---- ### 如何應用 求子矩陣 ($x_1 , y_1$)~($x_2 , y_2$) 的和。 由遞推的算式可得 ($x_1 , y_1$)~($x_2 , y_2$) 的區間和為: $ans = sum_{x2,y2} - sum_{x1-1,y2} - sum_{x2,y1-1} + sum_{x1-1,y1-1}$ ---- 圖例: $sum_{x2,y2} - sum_{x1-1,y2} - sum_{x2,y1-1} + sum_{x1-1,y1-1}$  ---- ### 例題： 對一段長度為 $n$ 的區間，做出 $q$ 筆詢問 * subtask 1: $n*q \le 10^8$ * subtask 2: $n \le 10^2,\ q \le 10^8$ * subtask 3: $n \le 10^6,\ q \le 10^8$ ---- ### subtask 1: $n*q \le 10^8$ 每次詢問就遍例一次，直接暴力加法 ```cpp= for(int i=1;i<=q;i++){ int l,r,ans=0; cin>>l>>r; for(int j=l;j<=r;j++){ ans+=arr[j]; } cout<<ans<<"\n"; } ``` 最差情況 : $q$ 次詢問都是求 $sum_{1,n}$ 因此你每次都需要遍例 $1~n$，則時間複雜度為 $O(q\cdot n)$ ---- ### subtask 2: $n \le 10^2,\ q \le 10^8$ 開 $10^2*10^2$ 的陣列，sum[i][j]紀錄 $i \sim j$ 的總和是多少 $q$ 筆詢問即可 $O(1)$ 解決掉 因此時間複雜度為 $O(n^2+q)$ ---- ### subtask 3: $n \le 10^6,\ q \le 10^8$ 開 $10^6$ 的陣列，sum[i] 紀錄 i 的前綴和是多少 q 筆詢問即可 $O(1)$ 解決掉 因此時間複雜度為O(n + q) ```cpp= int n,l,r,q; int arr[N]={},sum[N]={}; cin>>n; for(int i=1;i<=n;i++){ cin>>arr[i]; sum[i]=sum[i-1]+arr[i]; } cin>>q; for(int i=1;i<=q;i++){ cin>>l>>r; cout<<sum[r]-sum[l-1]<<"\n"; } ``` --- ## 差分 ---- ### 差分的構造 差分是一種和前綴和相對的策略，可以當做是求和的逆運算。 $f_{i} = arr_{i} - arr_{i-1}$ , $f_{1} = arr_{1}$ ```cpp= ex: arr[] = 1 10 5 -3 9 f[] = 1 9 -5 -8 12 ``` 同時不難發現，$arr_{i} 的值是 f_{i} 的前綴和$ ---- ## 計算區間和 若你要利用f計算arr的前綴和 $sum_{1,n} = \sum\limits_{i = 1}^n \sum\limits_{j = 1}^i {f_j}=\sum\limits_{i = 1}^n (n-i+1)*f_{i}$ ## 以及修改區間值 若你要再$arr_l$ ~ $arr_r$ 都加上 x 只需要修改 $f_l$ 和 $f_{r+1}$ 的值 ```cpp= f[l] += x; f[r+1] -= x; ``` ---- ### 例題： 對一段長度為 $n$ 的區間，提出 $k$ 次區間修改後詢問你一次結果 * subtask 1: $n*k \le 10^8$ * subtask 2: $n \le 10^6,k \le 10^8$ ---- ### subtask 1: $n*k \le 10^8$ 一樣直接暴力做，這邊就不贅述 ---- ### subtask 2: $n \le 10^6,\ k \le 10^8$ ```cpp= int n,l,r,k,x; int arr[N]={},f[N]={}; cin>>n; for(int i=1;i<=n;i++){ cin>>arr[i]; f[i]=arr[i]-arr[i-1]; } cin>>k; for(int i=1;i<=k;i++){ cin>>l>>r>>x; f[r+1]-=x,f[l]+=x; } ``` --- 今天教的三個內容都是關於優化，都很常用，回家請好好練習 :p ---- # 練習時間 :) 問啥都行 題單:https://vjudge.net/contest/532352 回饋表單(想檢討上週題目可以進來反應，全匿名) https://forms.gle/7ZY16mxu6BzaFsHaA