题目描述
N 个数的全排列有 N! 种，比如 5 个数的排列有 5!=120 种。但是，前面的置换 ( 3 4 5 2 1 ) 我们看到，置换 6 次后，数列就还原了。

显然，置换( 3 4 5 2 1 )只能得到 6 个不同的排列，或称这个置换的周期是 6 。

当 N 比较大时，周期有可能回很大！

为了研究这个问题，数学家先简化问题：研究单独一个“数”的周期！

例如置换( 3 4 5 2 1 )的规律：

1. 原始数列 1 2 3 4 5

2. 第 1 次置换后 5 4 1 2 3

3. 第 2 次置换后 3 2 5 4 1

4. 第 3 次置换后 1 4 3 2 5

5. 第 4 次置换后 5 2 1 4 3

6. 第 5 次置换后 3 4 5 2 1

7. 第 6 次置换后 1 2 3 4 5

......

因此:

• 数字 1 的位置变化为：1—3—5—1—3—5—1…， 显然数字1的周期就是 3 。

• 数字 2 的位置变化为：2—4—2—4—2—4…， 显然数字2的周期就是 2 。

• 数字 3 的位置变化为：3—5—1—3—5—1—3…， 显然数字3的周期就是 3 。

• 数字 4 的位置变化为：4—2—4—2—4—2…， 显然数字4的周期就是 2 。

......

结论：各个数的周期分别是：3 2 3 2 3。

输入格式

第一行 1 个正整数：N，范围在[1,100]，表示字符串长度。

第二行：有 N 个整数，为 1 到N的一个全排列，表示一个置换。

输出格式

一行，N 个数。第 i 个数表示第 1 个数经过多少次又变化回来。

样例

5
5 3 2 1 4

3 2 2 3 3

解题思路分析

上一个版本的程序存在一个问题：存在大量的重复计算。其实，从 i 跳到 jump[i]，再跳到 jump[jump[i]] ... 最后跳回 i ，这里的这一段数字就是构成了一个首尾相连的环。他们的循环节都一样，所以，不需要每个 i 都算一次 work(i)。我们可以对 work( ) 做一下改进，每次算出 i 的周期试，就把一批数字都设置 ans 值。在 main 函数里，只对那些 ans[i]==0 的情况才调用 work 函数。

完善程序

#include<bits/stdc++.h>
using namespace std;
int jump[1000001],n,ans[1000001];
void work(int i)
{
	int cnt=填空(1),ii=i;
	i = jump[i];
	while(i!=ii)
	{
		i = 填空(2);
		填空(3);
	}
	// 跳了 cnt 次就会变回 i 
	
	i=ii;
	while(填空(4))
	{
		ans[i] = 填空(5);
		i=jump[i];
	}
}
int main()
{
	
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&jump[i]);

	for(int i=1;i<=n;i++)
	{
		if(填空(6)) // 如果 ans[i] 不为 0，表示之前已经计算过了		
			work(i);	
	}
		
	for(int i=1;i<=n;i++)
		printf("%d ",ans[i]);
	
	return 0;
}

填空(1):{{ input(1) }}

填空(2):{{ input(2) }}

填空(3):{{ input(3) }}

填空(4):{{ input(4) }}

填空(5):{{ input(5) }}

填空(6):{{ input(6) }}