程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 1721 CARDS(置換)

poj 1721 CARDS(置換)

編輯：C++入門知識

大致題意：原始序列通過洗牌機洗牌s次後變為當前序列，已知當前序列，求原始序列。

在置換群快速冪運算研究與探討中最後有詳解，有兩種解法，一種是求出置換的長度a（即一副牌洗a次後變回原來的位置）,現已知原始序列置換s次變為當前序列，那麼當前序列再置換a-s次就是原始序列了。求a就是直接模擬每個置換的過程，直到某序列與當前序列相等。另一種是置換的開方，相當於原始序列的2^s冪是當前序列，將當前序列開2^s次方便是原始序列。

第二種方法暫時還不會，先貼第一種。

#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#define LL long long
#define _LL __int64
#define eps 1e-8
#define PI acos(-1.0)
using namespace std;

const int maxn = 1010;
const int INF = 0x3f3f3f3f;
int n,s;
int a[maxn],b[maxn],c[maxn];

//求置換的長度a
int solve()
{
	int cnt = 0,i;
	while(1)
	{
		for(i = 1; i <= n; i++)
			b[i] = c[c[i]];
		cnt++;
		for(i = 1; i <= n; i++)
			if(a[i] != b[i])
				break;

		if(i > n)
			break;
		for(i = 1; i <= n; i++)
			c[i] = b[i];
	}
	return cnt;
}

int main()
{
	while(~scanf(%d %d,&n,&s))
	{
		for(int i = 1; i <= n; i++)
		{
			scanf(%d,&a[i]);
			b[i] = a[i];
			c[i] = a[i];
		}

		int cnt = solve();
		s %= cnt;
		s = cnt - s;
		while(s--)
		{
			for(int i = 1; i <= n; i++)
				b[i] = a[a[i]];
			for(int i = 1; i <= n; i++)
				a[i] = b[i];
		}
		for(int i = 1; i <= n; i++)
			printf(%d
,b[i]);

	}
	return 0;
}