倍增算法（含L3-1 银白之森题解）

本文背景

天梯赛后被建议来吃吃“银白之森”这坨，吃完了认为确实是一坨，故写本文来介绍一下这个题所涉及到的倍增算法。

朴素倍增

对于这样一个问题：

从0出发，到7格外的位置上，如何快速转移你的位置。

最简单最暴力的算法就是一格一格走（但是给到 $ 1≤k≤10^{12} $ 你不就炸了吗？）。

于是看这个数的二进制，发现：

任何一个数都可以用$ n $个$ 2^k $的和来表示。

则对于这样一个图：

我们发现从0到7需要跨越 $ 7_{10} (111_2) $格，即 $ 7 = 2^0 + 2^1 + 2^2 $，于是我们建立一个状态表示数组$ f $，使得 $ f[i][j] $ 表示从1出发，跨越$ 2^{j} $ 步所到达的地方。

以这个图为例：我们依次经过$ f[0][0]=1,f[1][1]=3,f[3][2]=7 $到达了第7格。

这时有人发现：

这样从$i$出发，走$2^{j}$格，就可以看成从$i$出发，走$2^{j-1}$格后到达$i+A$，再走$2^{j-1}$格到达目的地，递推关系如下：

所以，如果我们预先处理好一个这样的状态表示数组$ f $，那查询的时候时间复杂度会大大降低，该算法的时间复杂度为$ O(n \log k) $。

Eg：L3-1 银白之森 作者：Chocola

题目描述 ：

在不知名的银白之森，共有 $n$ 个节点。

每个节点处，生活着一名魔法师。在每个节点，有一条通向其他节点的单向道路。

不知道该说运气好还是不好，你被一阵神秘的力量所影响，落在了某个节点上。接下来你可以沿着这些单向道路移动 $k$ 次。每利用单向道路移动到一个节点，这个节点处的魔法师会为你进行一次赐福，获得等于节点编号数量的命定之缘。（例如，当节点编号为 3 时，经过这个节点可以获得 3 个命定之缘）。

需要注意的是，反复经过同一个节点时，可以重复获得命定之缘。

非常幸运，你提前掌握了整个银白之森的道路图。但同时非常不幸，你会被神秘的力量丢到某个随机的节点上 $q$ 次。那么，聪明如你，能求出来这 $q$ 次移动分别能获得多少命定之缘吗？

输入格式 ：

一行两个正整数 $ n $ 和 $ q $ ，表示银白之森总共有 $ n $ 个节点，编号为 1 到 $ n $ 。总共会有 $ q $ 次神秘力量。 $(1≤n,q≤100,000 )$

接下来一行 $ n $ 个整数，第 $ i $ 个整数表示节点 $ i $ 处的单向道路通向哪个节点。（保证范围在 $ [1,n] $ 内，单向道路可以指向自己）

接下来 $ q $ 行，每行两个整数 $ x,k $ ，表示你该次神秘力量影响下落在了点$ x $ 处，你可以沿着单向道路移动 $ k $ 次获得赐福。$(1≤x≤n ，1≤k≤10^{12})$

输出格式 ：

共 $ q $ 行，每行表示一次神秘力量影响下，你通过赐福获得的命定之缘的数量。

输入样例：

1
2
3
4

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

输出样例：

1
2

11 
29 

样例解释

第一次移动路径：1 -> 2 -> 3 -> 1 -> 2 -> 3

获得的命定之缘共计2 + 3 + 1 + 2 + 3 = 11

第二次移动路径：4 -> 5 -> 6 -> 6 -> 6 -> 6

获得的命定之缘共计5 + 6 + 6 + 6 + 6 = 29

分析

由于每个点只有一个固定的出边，所以每个点走 步后获得的命定之缘数量以及走到了哪一个点是可以确定的。

我们采用倍增的方式去维护每个点走 $ 2^{0},2^{1},2^{2},2^{3},2^{4}…2^{50} $ 后到达的位置以及获得的命定之缘的数量，每次询问时，将$ k $拆解成二进制数，快速跳转并计算贡献即可。

代码实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#include "bits/stdc++.h"
#define int long long
using namespace std;
const int N = 1e5 + 10; //100005

int dp[N][65];
int sum[N][65];
void solve()
{
	int n, q;
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> dp[i][0];
		sum[i][0] = dp[i][0];
	}
	for (int j = 1; j <= 63; j++) {
		for (int i = 1; i <= n; i++) {
			dp[i][j] = dp[dp[i][j - 1]][j - 1];
			//计算每个点出发走不同的2^j步可能到达的点
			sum[i][j] = sum[i][j - 1] + sum[dp[i][j - 1]][j - 1];
			//记录走2^j的步到这的命定之缘的和
		}
	}
	while(q --) {
		long long  x, k, ans = 0;
		cin >> x >> k;
		for(int i=63;i>=0;i--) {
			if(k >> i & 1) 
             //依次从高往低取k的二进制位
			{
				ans += sum[x][i];
				x = dp[x][i];
				k -= (1ll << i);
				//把1的二进制左移，在k上减去此次移动的步数
			}
		}
		cout << ans << endl;
	}
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int _ = 1;
//  cin >> _ ;
	while(_--)
	{
		solve();
	}
	return 0;
}