2020牛客暑期多校訓練營（第二場）J.Just Shuffle（逆元+模拟）

J-Just Shuffle

題意：給定一個排列A和一個大質數k，找出一個置換B，使得P經過k次B置換後得到A，輸出第一次置換後的結果

題解：在排列A上找出所有環，記環的大小為 s z i sz_{i} szi​，每一步移動的長度為 t m p i tmp_{i} tmpi​，使得 t m p i ∗ k ≡ 1 m o d s z i tmp_{i}*k\equiv1 mod sz_{i} tmpi​∗k≡1modszi​，也就是求出k在 m o d s z i modsz_{i} modszi​下的逆元，k為大質數，是以一定有解，輸出每個環移動 t m p i tmp_{i} tmpi​之後的結果

Code：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define pii pair<int, int>
#define pdd pair<db, db>
#define mem(a, b) memset(a, b, sizeof(a));
#define lowbit(x) (x & -x)
#define lrt nl, mid, rt << 1
#define rrt mid + 1, nr, rt << 1 | 1
template <typename T>
inline void read(T& t) {
    t = 0;
    int f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        t = t * 10 + ch - '0';
        ch = getchar();
    }
    t *= f;
}
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const ll Inf = 0x7f7f7f7f7f7f7f7f;
const int inf = 0x7f7f7f7f;
const db eps = 1e-5;
const db Pi = acos(-1);
const int maxn = 1e5 + 10;

int an[maxn];
int vis[maxn];
int res[maxn];
vector<int> vt;

int main(void) {
    int n;
    ll k;
    read(n), read(k);
    for (int i = 1; i <= n; i++)
        read(an[i]);
    for (int i = 1; i <= n; i++) {
        if (vis[i])
            continue;
        int pos = i;
        vt.clear();
        while (!vis[pos]) {
            vis[pos] = 1;
            vt.push_back(pos);
            pos = an[pos];
        }
        int sz = vt.size();
        int tmp = 0;
        while (tmp < sz) { //當sz等于1時，相當于自環，不移動
            if ((ll)tmp * k % sz == 1) //計算逆元
                break;
            tmp++;
        }
        for (int i = 0; i < sz; i++)
            res[vt[i]] = vt[(i + tmp) % sz];
    }
    for (int i = 1; i <= n; i++)
        printf("%d ", res[i]);
    return 0;
}