abc377_E

标签：std int res long i64 vis abc377

E - Permute K times 2

思路

这题由于序列P是一个排列，所以将P表示成一个图的时候，这个图将由\(m\)个环构成

对于每个环上的点来说，第一回合它会移动到距离它为\(2\)的点上，距离它为\(2\)的点同时也以相同的方式移动，那么第二回合，它就会移动到距离它为\(4\)的点上，得出规律，一个点移动\(k\)回合会移动到距离它为\(2^k\)的点上，由于是在一个环上移动，所以直接取模环的长度即可

代码

这里直接使用jiangly的代码了，很简洁优美

//来自jiangly
#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

int power(int a, i64 b, int p) {
    int res = 1;
    for (; b; b /= 2, a = 1LL * a * a % p) {
        if (b & 1) {
            res = 1LL * res * a % p;
        }
    }
    return res;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N;
    i64 K;
    std::cin >> N >> K;
    
    std::vector<int> P(N);
    for (int i = 0; i < N; i++) {
        std::cin >> P[i];
        P[i]--;
    }
    
    std::vector<bool> vis(N);
    for (int i = 0; i < N; i++) {
        if (vis[i]) {
            continue;
        }
        
        int j = i;
        std::vector<int> a;
        while (!vis[j]) {
            vis[j] = true;
            a.push_back(j);
            j = P[j];
        }
        
        i64 d = power(2, K, a.size());
        for (int x = 0; x < a.size(); x++) {
            P[a[x]] = a[(x + d) % a.size()];
        }
    }
    for (int i = 0; i < N; i++) {
        std::cout << P[i] + 1 << " \n"[i == N - 1];
    }
    
    return 0;
}

标签：std,int,res,long,i64,vis,abc377
From： https://www.cnblogs.com/mgnisme/p/18504788