题目翻译#

问题陈述#

给定一个长度为 $N$ 的序列 $X$ ，其中每个元素介于 $1$ 和 $N$ 之间（含两个元素），以及一个长度为 $N$ 的序列 $A$ 。

打印对 $A$ 执行以下操作 $K$ 次的结果。

将 $A$ 替换为 $B$ ，使得 $B_i = A_{X_i}$ 。

数据范围#

所有输入值均为整数。
$1 \le N \le 2 \times 10^5$
$0 \le K \le 10^{18}$
$1 \le X _ i \le N$
$1 \le A _ i \le 2 \times 10^5$

解题思路#

对于这类进行单一重复操作且数据范围异常大 $(0 \le K \le 10^{18})$ 的题目，我们可以考虑倍增。

以 $Testcase$ $1$ 为例。

原输入为：

1
7 3
2
5 2 6 3 1 4 6
3
1 2 3 5 7 9 11

我们先模拟 $1$ 次操作：

1
7 2 9 3 1 5 9

在上面的基础上再模拟 $1$ 次：

1
1 2 5 9 7 3 5

这样，我们就可以将两步合并为一步，跳过第 $1$ 次的模拟，只需要 $\dfrac k 2$ 次操作即可获得我们需要的数组。

继续进行合并， $4$ 步、 $8$ 步、 $16$ 步、 $32$ 步…… $k$ 次操作便能很快完成。

如果 $k$ 为奇数，需要先操作一次将其转换为偶数再进行倍增。

时间复杂度： $O(n\log _k)$ 。

倍增思想在快速幂算法、求 $LCA$ (最近公共祖先) 中均有应用，可以大大降低重复操作的时间复杂度。

此外，本题还有时间复杂度为 $O(n)$ 的图论做法，可自行阅读官方题解。

完整代码#

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
#define endl '\n'
5
int n, k;
6

7
signed main(){
8
  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); //cin cout 优化
9
  cin >> n >> k;
10
  vector<int> x(n);
11
  vector<int> y(n);
12
  for(int i = 0; i < n; i++){
13
    cin >> x[i];
14
    x[i]--; //下标从0开始
15
  }
16
  iota(y.begin(), y.end(), 0); //将 y 赋值为0 ~ n-1
17
  while(k > 0){
18
    if(k % 2 == 1){ //k为奇数则操作一次
19
      for(int i = 0; i < n; i++){
20
        y[i] = x[y[i]];
21
      }
22
    }
23

24
    vector<int> tmp(n);
25
    for(int i = 0; i < n; i++){
26
      tmp[i] = x[x[i]];
27
    }
28
    x = move(tmp); //将tmp直接覆盖到x上，时间复杂度 O(1)
29
    k /= 2; //倍增
30
  }
31
  vector<int> a(n);
32
  vector<int> b(n);
33
  for(int i = 0; i < n; i++){
34
    cin >> a[i];
35
  }
36
  for(int i = 0; i < n; i++){
37
    b[i] = a[y[i]];
38
    cout << b[i] << " \n"[i == N - 1];
39
  }
40
  return 0;
41
}