Codeforces - 542C - Idempotent functions（思维 + 数学、*2000）

542C - Idempotent functions（⇔源地址）

• 542C - Idempotent functions（⇔源地址）
  • tag
  • 题意
  • 思路
  • AC代码
  • 错误次数：1

tag

*2000 + 构造 + 图论 + 数学 。没看太大出来这道题跟构造的关联，主要可能更靠思维，与图论的关联也比较弱（具有图论的性质，但是跟图论的算法无关）。题目非常不友好，看不懂……

个人评：*2000 + 思维 + 数学 。

题意

定义 a[x] 是 Idempotent 的，当 a[a[x]] == a[x] 时。

定义 \(f^{(1)}(x)\) 是 a[x] ，$f^{(2)}(x) = f^{{(1)}\big( f}{(1)}(x)\big)\ $ 是 a[a[x]] ，$f^{(3)}(x) = f^{(1)}\big(\ f^{(2)}(x) \big)\ $ 是 a[a[a[x]]] ，以此类推。

找到最小的 \(k\) ，使得对于 \(\forall x \in [1,n]\) ，\(f^{(k)}(x)\) 都是 Idempotent 的。

思路

题干较为难度，其中包含了一层隐藏的含义，即，只要 \(f^{(k)}(x)\) 能变化出来一个 \(f^{(t)}(x),(t \le k)\) 是 Idempotent 的，那么 \(f^{(k)}(x)\) 就是 Idempotent 的。

以下思路参考自 这一篇博客 。

展开推导之后发现，随着 \(k\) 增大，\(f^{(k)}(x)\) 的值必定会进入一个循环节，而循环节的长度最大不超过 a 数组的大小。这其实跟一张有向图一样，题目中有图论标签的原因或许正在于此。

有了隐含意思的解释，我们很容易的发现，我们找到每一个 \(f^{(k)}(x)\) 的循环节，答案即为这些循环节的最大公倍数。而本题另一个难点随之而来，我们发现，在进入循环节之前可能会有一段多余的变化（如下例的 \(x = 9\) 的情况），所以还需保证 \(k\) 大于这段多余变化的长度。

附样例：

9
5 6 7 4 2 5 1 3 8

其变换方式依次：

5 6 7 4 2 5 1 3 8
2 5 1 4 6 2 5 7 3
6 2 5 4 5 6 2 1 7

5 6 2 4 2 5 6 5 1
2 5 6 4 6 2 5 2 5
6 2 5 4 5 6 2 6 2

5 6 2 4 2 5 6 5 6
2 5 6 4 6 2 5 2 5
6 2 5 4 5 6 2 6 2

5 6 2 4 2 5 6 5 6
2 5 6 4 6 2 5 2 5
6 2 5 4 5 6 2 6 2

AC代码

int a[N], vis[N];
signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int n; cin >> n;
	for (int i = 1; i <= n; ++ i) cin >> a[i];
	
	int ans = 1, start = 0;
	for (int i = 1; i <= n; ++ i) {
		int x = a[i], len = 0;
		fill(vis + 1, vis + 1 + n, 0);
		while (!vis[x]) {
			vis[x] = ++ len; // 记录第一次查找到这个位置的时间戳
			x = a[x];
		}
		// 循环节开始时间戳：vis[x]
		// 循环节长度：len - vis[x] + 1
		start = max(start, vis[x] - 1);
		ans = lcm(ans, len - vis[x] + 1);
	}
	
	for (int i = 1; ; ++ i) {
		if (ans * i > start) return cout << ans * i, 0;
	}
	
	return 0;
}

错误次数：1

处理多余变换时没有到位，没有完全处理掉。

文 / WIDA
2022.12.25 成文
首发于WIDA个人博客，仅供学习讨论