P7981 [JRKSJ R3] system

P7981 [JRKSJ R3] system

建图

看到这题，容易想到 \(i\rightarrow a_i\)，那么这个过程实际上形成了基环树森林。接下来分析操作在图上的变化。

我们以环上的每个节点作为根，手玩之后就可以发现，经过 \(k\) 次操作后，每个节点的值就是 \(2^k\) 级父亲（包括自己）。虽然这样不够严谨，因为跳完之后会在环上绕圈。由于每棵树的深度 \(\le \log n\)，我们可以先做 \(\log n\) 次操作，操作后的图中树的深度就变成 \(0\) 和 \(1\) 了。

对于环上的节点，还需要跳 \(2^{k-\log n}\) 次，假设环长为 \(l\)，那么最后位置就是 \(2^{k-\log n}\bmod l\)，显然只需要确定一个起点，接下来的点都是一一对应的，顺下去更新 \(ans\)，就可以，复杂度 \(O(n)\)。

深度为 \(0\) 没有儿子，不用管；深度为 \(1\) 的节点，由于比 \(a_i\) 少跳一次，最后的位置就是 \(pre_{ans_{a_i}}\)，\(pre\) 在遍历环时就可以更新。

复杂度 \(O(n\log k)\)。

#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define fi first
#define se second
#define pb push_back

typedef long long i64;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 5e5 + 10;
i64 n, k;
i64 a[N], b[N], vis[N], bel[N], pre[N], ans[N];
void work() {
	for(int i = 1; i <= n; i++) b[i] = a[a[i]];
	for(int i = 1; i <= n; i++) a[i] = b[i];
	return;
}
i64 qpow(i64 a, i64 b, i64 m) {
	i64 ret = 1;
	while(b) {
		if(b & 1) ret = ret * a % m;
		a = a * a % m;
		b >>= 1;
	}
	return ret;
}
void Solve() {
	std::cin >> n >> k;

	for(int i = 1; i <= n; i++) {
		std::cin >> a[i];
	}
	i64 lg = log2(n) - 1;
	while(lg && k) {
		lg--, k--;
		work();
	}
	if(!k) {
		for(int i = 1; i <= n; i++) std::cout << a[i] << " \n"[i == n];
		return;
	}
	for(int i = 1; i <= n; i++) {
		if(vis[i]) continue;

		i64 now = i;
		for(; !vis[now]; now = a[now]) vis[now] = 1;
		if(bel[now]) continue;

		i64 cnt = 0;
		for(; !bel[now]; now = a[now]) bel[now] = 1, cnt++, pre[a[now]] = now;

		i64 t = qpow(2, k, cnt), st = now, ed = now;
		while(t--) ed = a[ed];

		ans[st] = ed;
		now = a[st], ed = a[ed];
		while(now != st) {
			ans[now] = ed;
			now = a[now], ed = a[ed];
		}
	}
	for(int i = 1; i <= n; i++) {
		if(!bel[i]) ans[i] = pre[ans[a[i]]];
	}
	for(int i = 1; i <= n; i++) std::cout << ans[i] << " \n"[i == n];
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
	Solve();

	return 0;
}