# 快速冪與倍增法 Binary Exponentiation and Lifting
本篇會細說快速冪與倍增法的原理，以圖示的方式探討兩者的關係
備註 : 倍增法的部分建議先讀過[樹的基本性質](https://hackmd.io/@ShanC/Trees-Basic-Properties)再回來讀
## 快速冪簡介
快速冪是一個處理整數冪次的演算法，可以在 $O(log ~n)$ 的複雜度完成任務
一般來說我們處理冪次問題 $a^{~n}$ 會使用以下方法:
```cpp
int ans = 1;
for(int i = 0; i < n; i++)
ans *= a;
cout << ans;
```
這種方法最直觀，但是卻需要 $O(n)$ 的時間才能完成。對於數字過大的數字實在太耗時，因此我們會需要用到快速冪來處理這個問題
## 快速冪原理說明
要解釋快速冪的原理，需要用到一個性質
### 二進制
每個十進制非負整數 $(n)_{10}$ 都可以被拆解成二進制
$(n)_{10}=a_0\times2^0+a_1\times2^1+...+a_k\times2^k$，其中 $a_i=0 ~or ~1, \forall ~i\in N$
則可寫成二進制: $(a_ka_{k-1}...a_1a_0)_2$
舉例來說: $(61)_{10}=1\times2^0+0\times2^1+1\times2^2+1\times2^3+1\times2^4+1\times2^5=(111101)_2$
換種角度來看，也可以將一個數字看作有一數列 $<2^{~n}>$
二進位就是看這數列中要取哪幾項相加才會是我要的數字
$1$ 就是取該項，$0$ 就是不取該項
### 快速冪原理
#### 原理說明
設今天有一個數字 $b^{~n}$，可以先把 $n$ 變成二進制的寫法
得到 $b^{~n}=b^{~(a_0\times2^0+a_1\times2^1+...+a_k\times2^k)}=b^{~a_0\times2^0}\times b^{~a_1\times2^1}\times...\times ~b^{~a_k\times2^k}$。其中，$a_i\in \{0, 1\}~(0\leq i\leq k)$
#### 列舉序列
要窮舉序列 $<b^{2^0}, b^{2^1}, b^{2^2},..., ~b^{2^k}>$ 是很簡單的，只需要先計算 $k$ 值，再使用 $for$ 迴圈就可以實現
```cpp
#define ll long long
void enumerate_sequence(ll b, ll n){
ll k = log2(n);
for(int i = 0; i <= k; i++){
b *= b;
}
}
```
#### 取 or 不取
再來就是要來判斷 $a_i$ 是 $0$ 還是 $1$。若 $1$ 則將答案乘上去， $0$ 就不理他
```cpp
#define ll long long
ll pick_sequence(ll b, ll n){
ll k = log2(n), ret = 1;
for(int i = 0; i <= k; i++){
if(n & (1 << i)) // 是 1 就乘上去
ret *= b;
b *= b;
}
return ret; // 回傳答案
}
```
### 舉例
$7^{97}=7^{~(1100001)_2}=7^{2^0}\times7^{2^6}\times7^{2^7}=7^{1}\times7^{32}\times7^{128}$
## 快速冪實作
可以用 $while$ 迴圈來實現，這樣就不需要 $k$ 值了
- 每次迴圈都重複 $n$ >>= $1$，這就相當於從左往右看 $n$ 的位元
- 判斷 $n$ 的每給位元是否為 $1$，是的話就乘起來
- 每次迴圈將 $b$ *= $b$，這就相當於在算第 $i$ 項時的 $b^{2^i}$
```cpp
#define ll long long
ll fpow(ll b, ll n){
ll ret = 1;
while(n){
if(n & 1)
ret *= b;
b *= b;
n >>= 1;
}
return ret;
}
```
## 圖解快速冪
快速冪，簡單來說就是用二進位本身的機制，去判斷每次到底要「跳」幾次冪。以下例子中，假設我們想要求 $7^7$，則我們知道 $7^7=7^{2^0+2^1+2^2}$
<center>
<img src="https://hackmd.io/_uploads/rkKDBqhvle.png" style="margin: 0 auto; display: block; width: 300px">
</center>
我們可以驚奇地發現，快速冪整個「跳」的過程可以畫成一條路徑 (path)。原本我們習慣的跳法是一步一步地跳；快速冪的跳法是 $2$ 的冪次步跳
## 倍增法簡介
不難發現，其實類似快速冪的方法也可以運用在連通圖的走訪，尤其適合在「兩點路徑唯一的圖」中進行此操作。在有向圖，[functional graph](https://hackmd.io/@ShanC/basic-graph-theory-2#Functional-Graph-Successor-Graph) 有時具有此特性；在無向圖，樹本身的定義 ([這篇的定義 D](https://hackmd.io/@ShanC/Trees-Basic-Properties)) 就滿足了這個性質。倍增法這個技巧，以樹狀資料結構的詢問最常見
<center>
<img src="https://hackmd.io/_uploads/ryLLHN48R.png" style="margin: 0 auto; display: block; width: 400px">
functional graph (擷取自海大競程講義)
</center>
## 樹狀結構的倍增法與實作
在一棵樹中，假設已給定根節點 (有根節點才能討論祖先是誰)。我們||~~的題目~~||會好奇任一個節點 $x$ 的上一代、上兩代、...、上 $m$ 代祖先是誰。根據樹的定義，任兩點的路徑都是唯一的，這意味著我們可以構造一個函數 $g(x, m)$ 來找 $x$ 的第 $m$ 代祖先。在數學上，這樣寫其實很夠了，但是在程式中，我們必須每個節點的前幾代祖先都先找到並定義清楚。
### 資料結構定義
在資料結構上，我們只需要定義一個二維陣列當作是類似上面的函數 $f(x, n)$ 就好了，不會很複雜，只是 $n$ 在這裡代表的是第 $2^n$ 代祖先
#### 輸入
一般來說，題目都會給每個節點的父節點，所以會有以下輸入 :
```cpp
int f[MXN][logN]; // MXN: 最大節點數、logN: 最大祖先數
cin >> n; // 輸入節點數量
for (int i = 2; i <= n; i++){
cin >> father >> x; // 輸入 x 的父節點、x
f[x][0] = father; // 父節點就是 2^0 倍祖先
}
```
其中，父節點就是 $2^0$ 倍祖先，所以可以直接存在 $f[x][0]$ 當中
#### 初始化
因為 $x$ 的第 $2^i$ 代祖先就會是 $x$ 的第 $2^{i-1}$ 代祖先的第 $2^{i-1}$ 代祖先
<center>
<img src="https://hackmd.io/_uploads/BkxwLs2vel.png" style="margin: 0 auto; display: block; width: 400px">
</center>
因此考慮遞迴式 $f(x, i)=\begin{cases}
\text{the father of x , if }i=0\\
f(f(x, i-1), i-1)\text{ , otherwise} \\
\end{cases}$
這邊我們使用[動態規劃法](https://hackmd.io/@ShanC/Intro-to-DP)當中的 bottom-up 手法來初始化整張圖
```cpp
// logN: 最大的祖先數
for (int i = 1; i < logN; i++) { // binary lifting
for (int x = 1; x <= n; x++) {
f[x][i] = f[f[x][i - 1]][i - 1];
}
}
```
要注意的是，有些節點是沒有第 $i$ 代祖先的，但是我們沒必要想那麼多。由於 $f$ 在宣告時就設為 $0$ 的緣故，因此對 $1$-based 圖的編號沒有影響
### 資料結構大小
我們都知道在競程中，圖論題目的節點數 `MXN` 最大差不多就是 $2\times 10^6$ 這個量級。而 $f(x, i)$ 中最大的 $i$ 當然就是取 $2$ 為底的對數，也就是 $\approx 20.9$，因此在上面的程式碼當中，`logN` 只要取大約 $21$ 就夠了
## 倍增法例題說明: [Company Queries I](https://cses.fi/problemset/task/1687/)
### 題目
給你一棵 $n$ 節點的樹，已知節點 $1$ 是根節點。共訪問 $q$ 次，求 $x$ 的第 $k$ 代祖先
### 限制
- $1 \le n,q \le 2 \cdot 10^5$
- $1 \le x \le n$
- $1 \le k \le n$
### 題解
把輸入輸出看清楚，之後再去看 $k$ 的二進位去判斷要「跳」到幾代祖先，用類似快速冪的方法來判斷就好了
### 程式實作
```cpp
/* 略 */
while (q--) {
cin >> x >> k;
for (int i = 0; i < logN; i++) {
if (k & (1 << i))
x = f[x][i];
}
cout << (x ? x : -1) << '\n';
}
/* 略 */
```
## 備註
- 二維陣列 `f` 通常會定義在全域，如此一來初始化就會是 $0$
- 矩陣乘法也可以快速冪，之後的章節會探討矩陣乘法的意義
- 競程題目數字最大 $10^{18}$，若要求 $a^{10^{18}}$，使用快速冪可以把迴圈數壓在 $60$ 以內
~~(幾乎就是常數了)~~
- 通常倍增法都會跟 LCA 一起出現，真的只有倍增法的裸題真的不多
- 本篇把快速冪與倍增法寫在一起是因為他們共用同一個觀念
- 最低共同祖先會在之後的章節提及
## 題目練習
[Zerojudge d636. 大爆炸bomb](https://zerojudge.tw/ShowProblem?problemid=d636)
[Zerojudge d219. 00374 - Big Mod](https://zerojudge.tw/ShowProblem?problemid=d219)
[Zerojudge k137. 次方練習](https://zerojudge.tw/ShowProblem?problemid=k137)
[CSES Exponentiation](https://cses.fi/problemset/task/1095)
[CSES Exponentiation II](https://cses.fi/problemset/task/1712/)
[CSES Company Queries I](https://cses.fi/problemset/task/1687/)
----
## 參考資料
[海大競程 - Special Graph & 0-1 BFS & 差分約束](https://hackmd.io/@LeeShoWhaodian/summer-advanced-graph#/1)
[海大競程 - Tree Algorithm 1](https://hackmd.io/@LeeShoWhaodian/2025Tree1#/)
----
> [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC)
> 作者: ShanC
> 更新: 2024/9/13
Sign in with Wallet
Connect another wallet