本文主要是介绍poj 1721 CARDS(置换)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://poj.org/problem?id=1721
大致题意：原始序列通过洗牌机洗牌s次后变为当前序列，已知当前序列，求原始序列。
在置换群快速幂运算 研究与探讨中最后有详解，有两种解法，一种是求出置换的长度a（即一副牌洗a次后变回原来的位置）,现已知原始序列置换s次变为当前序列，那么当前序列再置换a-s次就是原始序列了。求a就是直接模拟每个置换的过程，直到某序列与当前序列相等。另一种是置换的开方，相当于原始序列的2^s幂是当前序列，将当前序列开2^s次方便是原始序列。
第二种方法暂时还不会，先贴第一种。
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#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\n",b[i]);}return 0;
}
这篇关于poj 1721 CARDS(置换)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
