题解 AtCoder Beginner Contest 367 E - Permute K times (*1370)

· · 题解

在博客园食用更佳：https://www.cnblogs.com/PinkRabbit/p/-/ABC367。

题意简述（*1370）

给定两个长度为 n 的整数序列 (a_1, \ldots, a_n) 和 (x_1, \ldots, x_n)，其中保证 1 \le x_i \le n。

求经过以下变换 k 次后的序列 a：

数据范围：n \le 2 \times 10^5，k \le 10^{18}，1 \le x_i \le n。

题解

注意到最后 a 的每个元素都是原先 a 的某个元素。若能快速求得变换 k 次后的 a 的第 i 位是原先 a 的第几位，则本题也迎刃而解。

把 1 \sim n 看作一张图中的结点，以每个 i 向对应的 x_i 连一条有向边，每个点恰好有一条出边。

可以看出，设从点 i 出发沿着出边走 k 次后到达点 p，则最后的第 i 位就是原先的第 p 位。

一张每个点恰好有一条出边的有向图是一片基环内向森林。至此本题被转化为基环内向森林上的“k 级祖先”问题。

可以通过倍增解决 k 级祖先问题：设 g(j, i) 表示从点 i 出发沿着出边走 2^j 次后到达的点，则有边界 g(0, i) = x_i 和转移 g(j + 1, i) = g(j, g(j, i))。要回答询问，只需将 k 进行二进制拆分，后对每个进制位 j 进行 p \gets g(j, p) 的跳跃即可。

时空复杂度为 \mathcal O(n \log k)。

注：由于这里的 k 级祖先可以离线询问，存在线性时空的做法。具体而言，找到每个连通块的环后进行 DFS，记录 DFS 栈，然后定位栈上从当前点往前数 k 位的点，或栈长不足 k 时定位环上的特定点。由于代码实现比倍增的做法复杂，不展示具体代码。

参考 AC 代码

#include <iostream>
#include <vector>
using std::cin, std::cout;

#define F(i, a, b) for(int i = a; i <= (b); ++i)

void Solve();
int main() {
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
    Solve();
    return 0;
}

using LL = long long;

void Solve() {
    int n;
    LL k;
    cin >> n >> k;
    std::vector<int> x[60], a(n + 1);
    x[0].resize(n + 1);
    F(i, 1, n)
        cin >> x[0][i];
    F(j, 0, 58) {
        x[j + 1].resize(n + 1);
        F(i, 1, n)
            x[j + 1][i] = x[j][x[j][i]];
    }
    F(i, 1, n)
        cin >> a[i];
    F(i, 1, n) {
        int p = i;
        F(j, 0, 59)
            if (k >> j & 1)
                p = x[j][p];
        cout << a[p] << " \n"[i == n];
    }
}