Trick
- 排列置换题，考虑转化乘环上移动问题。
题目
精灵之环
假设知道排列 \(p\)。
那么把这个排列 \(p\) 的环连出来，环上点的编号是排列的下标，点的值是编号对应的值。
就比如排列 4 1 2 3 的环为：
val: 4 1 2 3 4
id : 1->2->3->4->1...
可以发现把这些环上的值移动一次会使得环上点的编号和值相等，此时就对应排列 \(1,2,3,4,\dots,n\)，也就是 \(p_0\)。
然后考虑把 \(p_k\) 的环给连出来，现在对于 \(p_k\) 的一个长度为 \(len\) 的环，如果有 \(\gcd(len,k)=1\)，那么就可以把这个环上的值移动 \(k\) 次变成编号与值对应相等的环。
如果不满足 \(\gcd(len,k)=1\)，那么可以考虑把若干个长度为 \(len\) 的环拼起来，使得 \(\gcd(len\times t,k)=t\)（\(t\) 为环的个数），这样也可以使得把这个环上的值移动 \(k\) 次变成编号与值对应相等的环。
所以对于每种长度的环，找到一个最小的 \(t\) 使得 \(\gcd(len\times t,k)=t\)，然后把这些环每 \(t\) 个拼一起即可，因为题目满足有解，所以一定能够找到这个 \(t\)。
知道了所有环，就可以求出 \(p\) 了。
代码
#include <bits/stdc++.h>void Freopen() {freopen(".in", "r", stdin);freopen(".out", "w", stdout);
}using namespace std;
const int N = 2e5 + 10, M = 2e5 + 10, inf = 1e9, mod = 998244353;int n, k;
int q[N], p[N];vector< int> G[N];
vector< int> cle[N], ans[N];vector< vector< int> > vec[N], V;int vis[N], mp[N], cnt;void dfs( int u, int id) {if (vis[u]) return ;vis[u] = 1, cle[id].push_back(u);for ( auto v : G[u]) dfs(v, id);
}signed main() {ios :: sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> k;for ( int i = 1; i <= n; i ++)cin >> p[i];for ( int i = 1; i <= n; i ++) G[p[i]].push_back(p[p[i]]);for ( int i = 1; i <= n; i ++)if (! vis[i]) dfs(i, ++ cnt);for ( int i = 1; i <= cnt; i ++) {int len = (int)cle[i].size();vec[len].push_back(cle[i]);mp[len] = 1;}int tot = 0;for ( int len = 1; len <= n; len ++) {if (! mp[len]) continue ;for ( auto v : vec[len]) {V.push_back(v);int siz = (int)V.size() * len;if (__gcd(k, siz) == (int)V.size()) { // 此时 V.size() 就是 t++ tot;ans[tot].resize(siz);for ( int i = 0; i < siz; i ++)vis[i] = 0;// 构造环for ( auto u : V) {int id = 0;for ( int i = 0; i < siz; i ++)if (! vis[i]) {id = i;break ;}for ( auto c : u)ans[tot][id] = c, vis[id] = 1,id = (id + k) % siz;}cnt = 0, V.clear();}}}// 最后在环上面移动一次就是 p（这里默认了环上的点编号与值相等，也就是 p_0 对应的环）for ( int i = 1; i <= tot; i ++) {int len = (int)ans[i].size();for ( int j = 0; j < len - 1; j ++)q[ans[i][j]] = ans[i][j + 1];q[ans[i][len - 1]] = ans[i][0];}for ( int i = 1; i <= n; i ++) cout << q[i] << ' ';cout << '\n';return 0;
}
)
)
)
