题解 P5151 【HKE与他的小朋友】

rui_er · 2021-09-24 21:40:47 · 题解

题意简单来讲就是给你一个置换 A，执行 k 次，问最后每个位置的数是啥。

我们知道两个置换的乘法：假设有置换 f=\begin{pmatrix}a_1 & a_2 & \cdots & a_n\\a_{p_1} & a_{p_2} & \cdots & a_{p_n}\end{pmatrix} 和 g=\begin{pmatrix}a_{p_1} & a_{p_2} & \cdots & a_{p_n}\\a_{q_1} & a_{q_2} & \cdots & a_{q_n}\end{pmatrix}，有 f\circ g=\begin{pmatrix}a_1 & a_2 & \cdots & a_n\\a_{q_1} & a_{q_2} & \cdots & a_{q_n}\end{pmatrix}。

我们可以用这个乘法运算代替整数乘法实现快速幂，即可在 O(n\log{k}) 的时间复杂度内求出 A^k。然后注意这个结果是一个置换，要知道最后第 i 个位置是几，就要看第二行为 i 的是第几个位置。

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
using namespace std;
typedef long long ll;
const int N = 1e5+5; 

int n, k;
template<typename T> void chkmin(T &x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T &x, T y) {if(x < y) x = y;}
struct Array {
    int p[N];
    Array() {memset(p, 0, sizeof(p));}
    Array(int n) {rep(i, 1, n) p[i] = i;}
    ~Array() {}
    friend Array operator * (const Array& a, const Array& b) {
        Array ans = Array(n);
        rep(i, 1, n) ans.p[i] = a.p[b.p[i]];
        return ans;
    }
    friend Array operator ^ (Array a, int k) {
        Array ans = Array(n);
        for(;k;k>>=1,a=a*a) if(k & 1) ans = ans * a;
        return ans;
    }
}a, b;

int main() {
    scanf("%d%d", &n, &k);
    rep(i, 1, n) scanf("%d", &a.p[i]);
    a = a ^ k;
    rep(i, 1, n) b.p[a.p[i]] = i;
    rep(i, 1, n) printf("%d%c", b.p[i], " \n"[i==n]);
    return 0;
}