每筆詢問都暴力走 $k$ 步要花上 $O(qk)$ 的時間，顯然是不可能的，所以我們勢必要有辦法「一次跳很多步」，像是如果我們想要能一次跳 $c$ 步，可以

• 先預處理從每個星球出發，走 $c$ 步會跳到哪裡。
• 處理一筆詢問時，先跳 $\lfloor k/c \rfloor$ 次 $c$ 步，剩下的 $k - \lfloor k/c \rfloor c = k \bmod c$ 步再一步一步走。

這樣就每筆詢問都只要跳最多 $k/c + c$ 次而已，而預處理會花上 $O(cn)$ 的時間。不過這樣做是不夠的，讀者可以自己算算看，讓 $k/c + c$ 最小的 $c$ 是 $\sqrt{k}$，這樣總時間複雜度會是 $O((n+q) \sqrt{k})$（這裡的 $k$ 是 $k$ 的最大值），以這題的範圍來說還是太慢了。

問題在於：

• $c$ 太小的話，$k / c$ 會很大。
• $c$ 太大的話，不只 $k \bmod c$ 會很大，預處理的時間也會很大。

所以要是我們只準備一種「跨大步的步數」，不太可能可以做得很快，但我們總得要準備一個很大的步數吧？要是想要可以一次走 $c$ 步，就得先花 $O(cn)$ 的時間預處理每個星球出發走 $c$ 步會抵達哪裡，那也沒辦法做到很大的 $c$，於是我們現在要面對的第一個問題，就是要怎麼預處理一個很大的步數。

既然處理詢問的時候可以跨大步，那預處理的時候當然也可以跨大步！如果我們知道每個星球出發走 $c/2$ 步會到哪裡，那只要走兩次 $c/2$ 步，就能算一個星球走 $c$ 步會到哪裡了。為了知道走 $c/2$ 步會到哪裡，那可以先知道走 $c/4$ 步會到哪，走兩次 $c/4$ 步就會知道走 $c/2$ 步會到哪……，發現了嗎？有點像是基礎數學 / 常用數學演算法裡面提到的快速冪，我們把第 $i$ 個星球出發走一步會到的星球記作 $f(i)=t_i$、走 $k$ 步會到的記作 $f^{(k)}(i) = \underbrace{f(f(\dots f}_{k \text{ 次}}(i))$，那麼：

• 我們一開始就知道 $f^{(1)}(i)$。
• 想要知道 $f^{(2)}(i)$，只需要算 $f^{(1)}(f^{(1)}(i))$。算出全部的 $f^{(2)}(i)$ 只要花 $O(n)$ 的時間。
• 想要知道 $f^{(4)}(i)$，只需要算 $f^{(2)}(f^{(2)}(i))$。算出全部的 $f^{(4)}(i)$ 只要花 $O(n)$ 的時間。
• 想要知道 $f^{(8)}(i)$，只需要算 $f^{(4)}(f^{(4)}(i))$。算出全部的 $f^{(8)}(i)$ 只要花 $O(n)$ 的時間。
• ……
• 想要知道 $f^{(2^\ell)}(i)$，只需要算 $f^{(2^{\ell-1})}(f^{(2^{\ell-1})}(i))$。算出全部的 $f^{(2^\ell)}(i)$ 只要花 $O(n)$ 的時間。

一路算到 $2^\ell$ 的話，預處理要花的時間全部只要 $O(\ell n)$。

那要怎麼處理詢問呢？別忘了我們在想要算出 $f^{(2^\ell)}(i)$ 的過程中，已經預處理好 $2^\ell$ 以內所有走二的冪次步數的答案了，所以只要像快速冪那樣，把 $k$ 二進位分解乘一些二的冪次相加，分開來走，就可以只花 $O(\log k)$ 的時間就知道 $f^{(k)}(i)$。別忘了 $\ell$ 至少要有 $\lfloor \log_2 k \rfloor$。

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n >> q;

    // 30 >= log_2 k
    vector f(30 + 1, vector<int>(n + 1));
    for (int i = 1; i <= n; i++)
        cin >> f[0][i];
    for (int i = 1; i <= 30; i++)
        for (int j = 1; j <= n; j++)
            f[i][j] = f[i - 1][f[i - 1][j]];
    
    while (q--) {
        int x, k;
        cin >> x >> k;
        for (int i = 0; i <= 30; i++)
            if ((k >> i) & 1) // k 二進位分解有 2^i
                x = f[i][x]; // 跳 2^i 步
        cout << x << "\n";
    }

}

總時間複雜度是 $O((n+q) \log \max k)$。

倍增法的意思就是像這樣每次增加兩倍，因為有 $2^k+2^k=2^{k+1}$、二進位分解又很好計算等等的特性，在這種要做某種很單純的固定操作很多次的問題，倍增法就是很好用的技巧。如果把剛才偷偷提到的快速冪用這樣的說法解釋：

• 「很單純的固定操作」就是把數字乘上 $a$。
• 從數字 $x$ 開始做 $2^i$ 次這個操作，那數字就會變成 $x \times a^{2^i}$，所以我們只要算 $a^{2^i}$ 就好了，不用對每種 $x$ 分開算。
• $a^{2^k} \times a^{2^k} = a^{2^k + 2^k} = a^{2^{k+1}}$。

所以快速冪的過程就是（如果需要 $\bmod$，請自己在腦裡補上 $\bmod$）：

• 我們一開始就知道 $a^{2^0}$。
• 想要知道 $a^{2^1}$，只需要算 $a^{2^0} \times a^{2^0}$。這只要花 $O(1)$ 的時間。
• 想要知道 $a^{2^2}$，只需要算 $a^{2^1} \times a^{2^1}$。這只要花 $O(1)$ 的時間。
• ……
• 想要知道 $a^{2^\ell}$，只需要算 $a^{2^{\ell-1}} \times a^{2^{\ell-1}}$。這只要花 $O(1)$ 的時間。

一路算到 $a^{2^\ell}$，只要花 $O(\ell)$ 的時間，而算出 $a^{b}$ 需要 $\ell \geq \lfloor \log_2 b \rfloor$，所以快速冪需要的時間是 $O(\log b)$。跟剛剛那題不太一樣的是，因為乘法這個操作太有規則了，不需要對每種數字分別計算做 $2^k$ 次操作的結果，而在剛剛的例題裡面則需要每個星球分開計算，不過它們的核心精神都是一樣的。

倍增法也不只可以單純用來找「做數次操作後的結果」，也可以是稍微複雜一點的問題：

如果把從 $i$ 開始走 $k$ 步的傳送門上寫的數字最大值記作 $g^{(k)}(i)$、$g^{(1)}(i)=g(i)=w_i$，那要注意 $g^{(2^k)}(i)$ 是不能直接只用 $g^{(2^{k-1})}$ 算出來的，而是要算
\[ g^{(2^k)}(i)=\max(g^{(2^{k-1})}(i), g^{(2^{k-1})}(f^{(2^{k-1})}(i))) \]
這句話的意思是，從 $i$ 開始走 $2^k$ 步，可以分成兩段，前面那段是從 $i$ 開始、走 $2^{k-1}$ 步，所以路上的最大值是 $g^{(2^{k-1})}(i)$、後面那段是從 $f^{(2^{k-1})}(i)$ 開始、走 $2^{k-1}$ 步，所以路上的最大值是 $g^{(2^{k-1})}(f^{(2^{k-1})}(i))$，兩個取較大值就是整條路的答案了。實作上就跟上一個例題幾乎一樣，先算完 $2^{k-1}$ 步的答案（包含 $f$ 和 $g$）後，就可以很輕鬆地算出 $2^k$ 步的答案。

這種思考過程有點像分治法，就是想著把要算的東西分成兩半、假設有兩半的答案後，想想要怎麼拼起來，然後如果需要用到所求答案本身以外的資訊，就再想想怎麼算。像是在這裡，題目所求的答案是 $g$，但是算 $g$ 的過程我們需要用 $f$，所以就要也算出 $f$。倍增法通常有比一般的分治更好的性質，像是

• 分兩半後的子問題長得一模一樣：例如快速冪，$a^{2^k}$ 會被分成 $a^{2^{k-1}}$ 和 $a^{2^{k-1}}$ 兩個子問題，長得一模一樣。在這種問題只需要算一遍子問題就好，通常會給出形如 $O(\log k)$ 的複雜度。
• 雖然分兩半後的子問題是不同問題，但子問題會被重複使用：例如在 Planets Queries I 中，$f^{(2^k)}(i)$ 會被分成 $x = f^{(2^{k-1})}(i)$ 和 $f^{(2^{k-1})}(x)$ 兩個子問題、$f^{(2^k)}(x)$ 會被分成 $y=f^{(2^{k-1})}(x)$ 和 $f^{(2^{k-1})}(y)$ 兩個子問題，它們都會用到 $f^{(k-1)}(x)$。在前面的程式碼裡面，那個 for (int i = 1; i <= 30; i++) 的迴圈每次會算出所有 $f^{(2^i)}(\cdot)$，其實就是在把分治遞迴樹上，從下數上來第 $i$ 層的答案全部一口氣算完。這種問題通常會給出形如 $O(n \log k)$ 的複雜度。

跟分治還有一個不太一樣的地方是，分治法的過程通常是 top-down 的，而倍增法則通常寫成 bottom-up 的形式，這是讓問題規模總是 $2^k$ 的一個好處，讓我們知道只要先算出所有規模是 $2^k$ 的問題，就能很輕鬆地算出所有規模是 $2^{k+1}$ 的問題。分治法和倍增法的思路一體兩面，當想到一種思路時感覺差了一點，不妨換個角度想想，實作時可以再選擇最方便的作法。