给你一个长度为 n 下标从 0 开始的整数数组 receiver 和一个整数 k 。
总共有 n 名玩家，玩家 编号 互不相同，且为 [0, n - 1] 中的整数。这些玩家玩一个传球游戏，receiver[i] 表示编号为 i 的玩家会传球给编号为 receiver[i] 的玩家。玩家可以传球给自己，也就是说 receiver[i] 可能等于 i 。
你需要从 n 名玩家中选择一名玩家作为游戏开始时唯一手中有球的玩家，球会被传 恰好 k 次。
如果选择编号为 x 的玩家作为开始玩家，定义函数 f(x) 表示从编号为 x 的玩家开始，k 次传球内所有接触过球玩家的编号之 和 ，如果有玩家多次触球，则 累加多次 。换句话说， f(x) = x + receiver[x] + receiver[receiver[x]] + ... + receiver^(k)[x] 。
你的任务时选择开始玩家 x ，目的是 最大化 f(x) 。
请你返回函数的 最大值 。
注意：receiver 可能含有重复元素。
示例 1：
传递次数
传球者编号
接球者编号
x + 所有接球者编号
2
1
2
1
3
2
1
0
3
3
0
2
5
4
2
1
6
```txt
输入：receiver = [2,0,1], k = 4
输出：6
解释：上表展示了从编号为 x = 2 开始的游戏过程。
从表中可知，f(2) 等于 6 。
6 是能得到最大的函数值。
所以输出为 6 。
```
示例 2：
传递次数
传球者编号
接球者编号
x + 所有接球者编号
4
1
4
3
7
2
3
2
9
3
2
1
10
```txt
输入：receiver = [1,1,1,2,3], k = 3
输出：10
解释：上表展示了从编号为 x = 4 开始的游戏过程。
从表中可知，f(4) 等于 10 。
10 是能得到最大的函数值。
所以输出为 10 。
```
提示：
1 <= receiver.length == n <= 10^50 <= receiver[i] <= n - 11 <= k <= 10^10
在传球游戏中最大化函数值
题目
给你一个长度为 n 下标从 0 开始的整数数组 receiver 和一个整数 k 。
总共有 n 名玩家，玩家 编号 互不相同，且为 [0, n - 1] 中的整数。这些玩家玩一个传球游戏，receiver[i] 表示编号为 i 的玩家会传球给编号为 receiver[i] 的玩家。玩家可以传球给自己，也就是说 receiver[i] 可能等于 i 。
你需要从 n 名玩家中选择一名玩家作为游戏开始时唯一手中有球的玩家，球会被传 恰好 k 次。
如果选择编号为 x 的玩家作为开始玩家，定义函数 f(x) 表示从编号为 x 的玩家开始，k 次传球内所有接触过球玩家的编号之 和 ，如果有玩家多次触球，则 累加多次 。换句话说， f(x) = x + receiver[x] + receiver[receiver[x]] + ... + receiver^(k)[x] 。
你的任务时选择开始玩家 x ，目的是 最大化 f(x) 。
请你返回函数的 最大值 。
注意：receiver 可能含有重复元素。
示例 1：
传递次数
传球者编号
接球者编号
x + 所有接球者编号
2
1
2
1
3
2
1
0
3
3
0
2
5
4
2
1
6
1 | 输入：receiver = [2,0,1], k = 4 |
示例 2：
传递次数
传球者编号
接球者编号
x + 所有接球者编号
4
1
4
3
7
2
3
2
9
3
2
1
10
1 | 输入：receiver = [1,1,1,2,3], k = 3 |
提示：
-
1 <= receiver.length == n <= 10^5 -
0 <= receiver[i] <= n - 1 1 <= k <= 10^10
题解
方法一：
思路
注意到图中存在环，且有可能不止一个。对于传球k次，在进入环后，可以$O(1)$计算环绕次数。如果预处理出了所有环的长度，以及各个环内所有元素和。非环内元素到环的距离以及到环路径上的元素和。做到这些后可以$O(1)$计算每个点作为球的起点的f值。
但是这样码量巨大，短时间内可能调不出来。
可以用$O(nlogn)$的倍增算法替代，简洁巧妙。
倍增法还是运用了动态规划的思想。
我们预处理出每个节点作为传球起点时，传球0，2，4，8，等2的幂次次数后球所处的位置。以及这些经过的点的编号和。
更准确的定义，$f_{i,j}$是从j位置移动$2^i$所到达的位置，$s_{i,j}$为从j位置移动$2^i$次中通经过点的编号和（不含移动$2^i$次后的点编号）。
显然可以初始化$f_{0,j} = receiver[j], s_{0,j} = j$
状态转移，对于已知i的第j个祖先，如何知道i的第2j个祖先？答案就是i的第j个祖先的第j个祖先。
所以有$f_{i,j} = f_{i-1, f_{i-1, j}}$。
同理可以合并两段路径和$s_{i,j} = s_{i-1,j}+s_{i-1, s_{i-1, j}}$
对于k的值最大为$10^{10}$，由于$2^{34}=17179869184>10^{10}$最多只需要处理到$f_{34, n}$
而我们已经预处理出每个点可以传2的幂次步数后的位置以及路径上的编号和。
由于k可以分解为不超过34个不同的2的幂次之和，（k的二进制位不超过34位），所以每个点计算的传球所花时间是$O(logn)$的。
代码
1 | class Solution { |