意图写出http://www.cnblogs.com/kuangbin/archive/2012/08/28/2661066.html这个东西的完善版。
1.置换,置换的运算
poj 2369 Permutations置换群中有一个定理:设T为一置换,e为单位置换,T^k=e,那么k的最小正整数解是T的拆分的所有循环长度的最小公倍数。
#include <cstdio> ; ? a : gcd(b, a % b);} int lcm(int a,int b){return a / gcd(a, b) * b;} int a[maxn]; int main() { int n; scanf("%d", &n); ; i <= n; i++) { scanf("%d", &a[i]); } ; ; i <= n; i++) { ; while(temp != i) { len++; temp = a[temp]; } ans = lcm(ans, len); } printf("%d\n", ans); ; }
PE真的巨坑,每个blocks结束之后要加一个换行,样例输出是有问题的。
注意一下,这个地方,和上一道比较,是一个倒过来的,倒过来的能明白吗。
#include <cstdio> #include <cstring> + ; ? a : gcd(b, a % b);} int lcm(int a,int b){return a / gcd(a, b) * b;} int n,k,x; int a[maxn], round[maxn]; char s[maxn], ss[maxn]; int main() { while(~scanf("%d", &n) && n) { ; i <= n; i++) scanf("%d", &a[i]); //找寻环节并记录。 ; i <= n; i++) { ; do { temp = a[temp]; len++; }while(temp != i); round[i] = len; } while(~scanf("%d", &k) && k) { getchar(); gets(s+); ); while(slen <= n) { s[++slen] = ' '; } s[n+] = '\0'; strcpy(ss+, s+); ; i <= n; i++) { int t = round[i] - k % round[i]; int temp = i; while(t--) { temp = a[temp]; } ss[i] = s[temp]; } printf(); } puts(""); } ; }