题目链接:https://vjudge.net/problem/POJ-1721
题目意思:给出一个n个数的序列和它已经历的变换次数s,让你求变换前的序列。变换规则:如果i位置是牌j,j位置是牌k,那么i位置就为牌k。
大体思路:求出置换的长度a(即一副牌洗a次后变回原来的位置),现已知原始序列置换s次变为当前序列,那么当前序列再置换a-s%a(注意s%a)次就是原始序列了。
求a就是直接模拟每个置换的过程,直到某序列与当前序列相等。
#include <iostream>
#include <cstring>
using namespace std;
const int maxn=1000+100;
int flag=1,cnt=0;
int n,m;
int a[maxn],b[maxn],c[maxn];
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[i]=a[i];
}
while(flag)
{
for(int i=1;i<=n;i++)
{
c[i]=a[a[i]];
}
for(int i=1;i<=n;i++)
{
a[i]=c[i];
}
for(int i=1;i<=n;i++)
{
flag=0;
if(b[i]!=c[i])
{
flag=1;
break;
}
}
cnt++;
}
int ans=cnt-m%cnt;//算出置换长度
while(ans--)
{
for(int i=1;i<=n;i++)
{
c[i]=a[a[i]];
}
for(int i=1;i<=n;i++)
{
a[i]=c[i];
}
}
for(int i=1;i<=n;i++) cout<<a[i]<<endl;
return 0;
}