题解 P5557 【旅行】

· · 题解

解题思路

首先，每个点有且只有一个出边的图构成内向基环森林。

设一共有 n 个点，不难证明：在内向基环森林上走 n 次出边，此时一定停留在环上。

明白这两个套路后，这题就简单许多了。

考虑建立倍增数组 e_{i,\,u} ，表示从点 u 出发走 2^i 次出边停留的位置。以便我们在 O(\log n) 的时间里查询走任意 \le n 次出边停留的位置。

因为走到环上时，想一直走必然是绕着这个环转圈，自然想到应该存下每个环的信息（例如大小，上面有哪些点，每个点在何位置等）。

因此对于每个点，我们先走 n 步，如引理所述，我们此时正在某个环上，如果这个环尚未被记录，我们绕着环走直到回到出发的位置顺便记录信息。

如何处理询问？还是基于那个引理。如果询问的 t 很小（< n），以至于我们无法判断终点是否处于环上，此时恰好倍增数组正是为这个范围服务的。否则令 t' = t - n ，即先走 n 步再走 t' 步，我们求出 n 步后位于环上的位置，而 t' 步都是在绕圈（周期为环的大小，设其为 s）。只有 t'\ \text{mod}\ s = (t_1^{t_2} - n)\ \text{mod}\ s 步是有用的，快速幂及减法的得到该余数，然后直接使用之前预处理环的信息来查询。

时间复杂度：O(n \log n + m \log t) 。

代码实现

#include <bits/stdc++.h>

inline int read() {
    char c; int x; for (c = getchar(); !isdigit(c); c = getchar());
    for (x = 0; isdigit(c); c = getchar()) { x = x * 10 + c - '0'; } return x;
}

inline int power(int x, int y, int mod, int res = 1) {
    for (; y; y >>= 1, x = 1ll * x * x % mod) {
        if (y & 1) { res = 1ll * res * x % mod; }
    } return res;
}

const int N = 5e5 + 5, L = 19;

int n, m, q, lgn, e[L][N], bln[N], pos[N];
std::vector<int> cyc[N];

int check(int x, int y) {
    if (x == 1) { return 1; }
    long long tmp = 1;
    for (; y; y--) {
        tmp *= x;
        if (tmp > n) { return -1; }
    } return tmp;
}

int jump(int u, int x) {
    for (int i = 0; i <= lgn; i++) {
        if (1 << i & x) { u = e[i][u]; }
    } return u;
}

int main() {
    n = read(); lgn = log(n) / log(2) + 1e-7;
    for (int i = 1; i <= n; i++) {
        e[0][i] = read(); bln[i] = -1;
    }
    for (int j = 1; j <= lgn; j++) {
        for (int i = 1; i <= n; i++) {
            e[j][i] = e[j - 1][e[j - 1][i]];
        }
    }
    for (int i = 1; i <= n; i++) {
        int u = e[lgn][e[lgn][i]];
        if (bln[u] == -1) {
            for (; bln[u] == -1; u = e[0][u]) {
                bln[u] = m; pos[u] = cyc[m].size();
                cyc[m].push_back(u);
            }
            m++;
        }
    }
    for (q = read(); q; q--) {  
        int u = read(), x = read(), y = read(), z = check(x, y);
        if (z == -1) {
            u = jump(u, n);
            int s = cyc[bln[u]].size();
            z = (power(x, y, s) + s - n % s) % s;
            u = cyc[bln[u]][(pos[u] + z) % s];
        } else {
            u = jump(u, z);
        } printf("%d\n", u);
    }
    return 0;
}