---
tags: 基礎算法
title: 倍增
---
:::info
#### [ECPC16 PJ](https://codeforces.com/gym/101147/problem/J)
#### [TIOJ 1341](https://tioj.ck.tp.edu.tw/problems/1341)
:::

:::success
# 快速冪 Exponentiating by Squaring

## 問題

- 求$n^m$

- ex: 求$7^{13}$

## 實作
- 將指數轉二進制 binary(13) = 1101
- 按照二進制dp計算$7^{[0,3]}$
- 用計算好的冪次表對照二進制的1和0計算結果
- 複雜度：$O(\log m)$

int pow(n, m) {
    int ret = 1;
    for (int power = m; power; power >>= 1, n *= n) {
        ret *= (power & 1?n:1);
    }
    return ret;
}

int mod = 1000000007;
int mi(int a, int b) { // return a^b
    if(b == 0) {
        return 1;
    }
    else {
        int k = mi(a, b/2);
        if(b % 2 == 1)return k*k%mod*a %mod;
        else return k*k %mod;
    }
}

:::

:::info
#### [TOJ 510](https://toj.tfcis.org/oj/pro/510/)
:::

:::success
# 倍增 Binary Lifting

## 問題

- $N$張牌洗$K$次，每次照給定陣列$F$洗牌，求結果

## 模擬解

- 迴圈暴力模擬

- 複雜度：$O(K)$

## 倍增解

- 把$K$轉成二進制
- 用$F$初始化倍增陣列shuffle
- shuffle$[n][m]$ -> 第n個位置的卡牌在洗$2^m$個回合後的位置
- 遞迴式：shuffle$[n][m]$ = shuffle$[$shuffle$[n][m-1]][m-1]$
- 用shuffle陣列對照K的二進制跳指定回合
- 複雜度：$O(\log K)$

//很久遠的AC code
//上面的shuffle在這裡叫dp
#include <cstdio>
#include <vector>
using namespace std;

vector<vector<int>> dp;
vector<int> temp, binary;
int B[300000], ans[300000]; //B -> begin

void decimalToBinary(long long x) {    //轉二進制
    while (x > 0) {
	    binary.push_back(x%2);
	    x /= 2;
	}
}
int main(void) {
    int N, cur;
    long long K;
    scanf("%d", &N);
    temp.resize(N);
    for (int i=0; i<N; i++) {
    	scanf("%d", &B[i]);
    }
    for (int i=0; i<N; i++) {
        scanf("%d", &temp[i]);
    }
    dp.push_back(temp);
    scanf("%lld", &K);
    decimalToBinary(K);
    int len = binary.size(), times = len-1;
    for (int i=1; i<=times; i++) {    //建構倍增陣列
	    for (int o=0; o<N; o++) {
		    temp[o] = dp[i-1][dp[i-1][o]-1];
	    }
	    dp.push_back(temp);
    }
    for (int i=0; i<N; i++) {    //用倍增陣列對照二進制模擬過程
	    cur = i;
	    for (int o=0; o<len; o++) {
		    if (binary[o]) cur = dp[o][cur] - 1;
	    }
	    ans[cur] = B[i];
    }
    printf("%d", ans[0]);
    for (int i=1; i<N; i++) {
	    printf(" %d", ans[i]);
    }
    printf("\n");

    return 0;
}
//這題輸出要絕對準確，不能多換行或空格

5
1 2 3 4 5
3 1 4 5 2
1

2 5 1 3 4

:::

:::info
#### [TIOJ 2172](https://tioj.ck.tp.edu.tw/problems/2172)
:::

:::success
# 最近(低)共同祖先 Lowest Common Ancestor

## 定義

- 兩個node的所有祖先中離根最遠，最深的一個


| n | f[n][0] | f[n][1] | f[n][2] |
| --- | ------------ | ------------ | ------------ |
| 0 | 1 | 4 | -1 |
| 1 | 4 | -1 | -1 |
| 2 | 9 | 5 | -1 |
| 3 | 9 | 5 | -1 |
| 4 | -1 | -1 | -1 |
| 5 | 4 | -1 | -1 |
| 6 | 1 | 4 | -1 |
| 7 | 9 | 5 | -1 |
| 8 | 5 | 4 | -1 |
| 9 | 5 | 4 | -1 |

- f[節點編號n][節點往上跳第$2^m$次方] -> n往上跳2^m次方的祖先的編號
- 遞迴式：f$[n][m]$ = f$[$f$[n][m-1]][m-1]$
- d[節點編號n] -> n的深度

vector<int> B;

void binary(int n) {
    B.clear();
    while(n > 0) {
        B.push_back(n%2);
        n /= 2;
    }
    reverse(B.begin(), B.end());
}

int LCA(int a, int b) {
    //1° 較深節點往上跳到較淺節點的深度
    if (d[a] < d[b]) swap(a, b);
    binary(d[a] - d[b]);

    for (int i=0; i<B.size(); i++) {
        if (B[i]) a = f[a][i];
    }
    if (a == b) return a;
    //2° 兩節點同時往上跳到LCA下一層
    else {
        for (int i = log(N); i >= 0; i--) {
            if (f[a][i] != f[b][i]) {
                a = f[a][i];
                b = f[b][i];
            }
        }
    }
    
    return f[a][0];
}

cin >> a >> b;
cout << LCA(a, b);

return 0;

:::