2020牛客暑期多校训练营（第二场）J

Description

给定排列的幂 (P^k)，构造排列 (P)。 (n le 10^5, k in [10^8,10^9]) 且 (k) 为素数。

Solution

将一个排列视为置换，其由若干个环构成

找到所有的环，遍历每一个环 (c)，设长度为 (l)

则我们需要找到 (t) 使得 (kt=1 (mod l))，暴力找即可

然后将 (c^t) 并入答案中即可

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1000005;

int n,k,a[N],ans[N];

signed main()
{
    ios::sync_with_stdio(false);

    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];

    for(int i=1;i<=n;i++) if(!ans[i])
    {
        vector <int> vec;
        vec.push_back(i);
        for(int p=a[i];p!=i;p=a[p]) vec.push_back(p);

        int l=vec.size();
        int t=1;
        while(t*k%l!=1 && t<l) ++t;

        for(int j=0;j<l;j++) ans[vec[j]]=vec[(j+t)%l];
    }

    for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
}