P7981-Solution

· · 题解

题面非常简洁，注意到一次操作之后，\,a_{i}\,的值会变为\,a_{a_{i}}\,，所以我们不妨建立一张图，并连出\,a_{i}\rightarrow i\,的边。

画出这样一张图之后，你会发现这张图有\,n\,个点\,n\,条边，由于可能存在自环，所以这张图是基环树森林（其中可能存在环是自环的基环树）

（样例 2 的图，\,x.y\,表示序号为\,x\,，\,a_x\,的值为\,y\,的点，自环 Graph Editor 画不出来...）

并且显然的，这是一个内向树森林，所有点的入度都为\,1\,，定义对于边\,u\rightarrow v\,，\,u\,为\,v\,的父亲，注意父亲可能是自己。

注意到这样一个事实：

第一次操作后，\,a_{i}\,的值会变为\,a_{a_{i}}\,；

第二次操作后，\,a_{i}\,的值会变为\,a_{a_{a_{a_{i}}}}\,（有\,4\,个\,a\,）；

第\,r\,次操作之后，\,a_{i}\,的值会变为

\,a_{_{\ddots{a_{i}}}}\,

（不知道看不看得清）总之就是有\,2^{r}\,个\,a\,，相当于是从点\,i\,开始，跳到父亲\,2^r\,次。

我们不妨对基环树的环和附属子树（设\,i\,是环上的点，那么断开其在环上的边，剩下的是一棵树，称其为附属子树）分开讨论。

先讨论附属子树，由于附属子树树高不超过\,\mathcal{O}(n)\,，所以对于附属子树上的点，至多只需要\,\mathcal{O}(\log n)\,次就能跳到环中。

所以我们可以先跳\,\left\lceil\log_{2}n\right\rceil\,次，这样基环树森林的附属子树的高都变为\,0\,或\,1\,了。高为\,0\,的附属子树不用管，对于高为\,1\,的附属子树，此时的\,a_{i}\,是\,i\,下一步要跳到的点，假设\,ans[p]\,为点\,p\,最终跳到的点，\,pre[p]\,为跳到\,p\,的点上一步跳到的点，那么点\,i\,最终跳到的点就是\,pre[ans[a_i]]\,。

那么我们现在只需要处理环以及\,pre\,数组就行了。

由于我们之前已经跳过\,\left\lceil\log_{2}n\right\rceil\,次，所以接下来我们只需要跳\,2^{k-\left\lceil\log_{2}n\right\rceil}\,就够了，假设环长为\,leng\,，那么显然每个点只需要跳\,2^{k-\left\lceil\log_{2}n\right\rceil}\operatorname{mod}leng\,次就够了。

注意这里不能每个点都跳这么多次，因为这显然对于每个点，最坏是\,\mathcal{O}(leng)\,的，最坏复杂度可能到达\,\mathcal{O}(n^2)\,，所以我们不妨钦定一个起点\,st\,，我们让\,st\,跳这么多次就够了，假设最后跳到\,ed\,，因为\,st\,的后一个点最终跳到的位置显然是\,ed\,的后一个点，递推即可，这是\,\mathcal{O}(1)\,的。

显然在递推的过程中，我们可以顺带处理出\,pre\,数组，所以这个问题我们也解决了。

至此，这道题的流程就结束了，瓶颈在于那个快速幂，总体上时间复杂度是\,\mathcal{O}(n\log k)\,的，可以通过，具体实现可以看带注释的代码。

#include <bits/stdc++.h>

namespace io
    // 省略快读快写
using namespace io;
namespace problems
{
    const int N = 500010;
    int n, k;
    int a[N], b[N], ans[N], pre[N];
    bool vis[N];
    int idc[N], cidx = 0, large;

    void go(void)
    {
        for (int i = 1; i <= n; ++ i)
            b[i] = a[a[i]];
        for (int i = 1; i <= n; ++ i)
            a[i] = b[i];
        return;
    }
    int ksm(int a, int b, int p)
    {
        int res = 1;
        while (b)
        {
            if (b & 1) res = 1ll * res * a % p;
            a = 1ll * a * a % p, b >>= 1;
        }
        return res;
    }

    int main(void)
    {
        memset(vis, false, sizeof(vis));

        read(n), read(k);
        for (int i = 1; i <= n; ++ i)
            read(a[i]);
        int lgn = log2(n) + 1;
        while (lgn && k)
        {
            -- lgn, -- k;
            go();
        }
        if (!k)
        {
            for (int i = 1; i <= n; ++ i)
                writesp(a[i]);
            puts(""); return 0;
        }
        for (int i = 1; i <= n; ++ i)
            if (!vis[i])
            {
                int now = i;
                for ( ; !vis[now]; now = a[now])
                    vis[now] = true;
                // 找环
                if (idc[now]) continue;
                // i 是附属子树上的点，找到了旧环
                ++ cidx, large = 0;
                int st = now;
                for ( ; !idc[now]; now = a[now])
                    idc[now] = cidx, pre[a[now]] = now, ++ large;
                // 给环编号
                int times = ksm(2, k, large);
                // 需要偏移 2^k 次，模数为环长 large
                now = st;
                while (times --)
                    now = a[now];
                ans[st] = now;
                // 找到起点对应的位置
                int x = st, y = now;
                x = a[x], y = a[y];
                while (x != st)
                {
                    ans[x] = y;
                    x = a[x], y = a[y];
                }
                // 将环上的点的答案处理掉
            }
        for (int i = 1; i <= n; ++ i)
            if (!idc[i])
            // 处理附属子树
                ans[i] = pre[ans[a[i]]];
        for (int i = 1; i <= n; ++ i)
            writesp(ans[i]);
        puts("");

        return 0;
    }
}

int main(void)
{
    problems::main();

    return 0;
}