题解：AT_abc367_e [ABC367E] Permute K times

· · 题解

首先有一个比较显然的暴力：对于每个 i，我们暴力枚举它跳 k 次的位置，复杂度为 O(nk)，无法通过。

long long n, k, x[N], a[N];
inline int jump(long long v, long long k) {
    for (int i = 1; i <= k; i++) v = x[v];
    return v;
}
void _main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> x[i];
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        cout << a[jump(i, k)] << ' ';
    }
}

当你的代码出现这样的写法时

for (int i = 1; i <= k; i++) v = x[v];

就可以考虑用倍增优化了。具体地，令 fa_{i,j} 表示 j 跳 2^i 次跳到的点。初始化 fa_{0,i}=x_i。有递推式：

fa_{i,j}=fa_{i-1,fa_{i-1,j}}

查询的时候，按二进制倍增跳即可。复杂度 O(n \log k)。

long long n, k, x[N], a[N], fa[65][N];
inline int jump(long long v, long long k) {
//  for (int i = 1; i <= k; i++) v = x[v];
//  return v;
    for (int i = 0; i <= 63; i++) {
        if ((1LL << i) & k) v = fa[i][v];
    }
    return v;
}

void _main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> x[i];
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i <= n; i++) fa[0][i] = x[i];
    for (int i = 1; i <= 63; i++) {
        for (int j = 1; j <= n; j++) {
            fa[i][j] = fa[i - 1][fa[i - 1][j]];
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << a[jump(i, k)] << ' ';
    }
}