---
tags: 基礎算法
title: 倍增法
---

# 倍增法
- [ ] [實作倍增練習](https://toj.tfcis.org/oj/pro/510/)
:::info
其實不用倍增也能過。。。
:::
:::success
$dp[i][j]$為數字i經過$2^j$回合之後到第幾個位置
$dp[i][0]$很快可以求出
對於$j>0$的情況，$dp[i][j] = dp[A[dp[i][j-1]]][j-1]$;

$A[i]$是第個位置的初始編號 (題目給的第一個sequence)
$A[dp[i][j-1]]$是數字i經過$2^{j-1}$回合後的位置。因為我們狀態是**數字$i$**，所以要查詢$A$陣列換成數字
:::

- [ ] [有趣的互動題](https://tioj.ck.tp.edu.tw/problems/1341)
:::info
不熟的可以用二分搜喔 (小心慢用)
:::
- [ ] [裸考古經典題](https://tioj.ck.tp.edu.tw/problems/2172)
:::info
LCA一定要會的方法
:::