置换群的轮换,置换群与对称群

POJ1026 题意：对字符串按照置换操作k次，求最后的结果。 题解 求出每一个位置循环的长度，最后操作时，k对长度取模为k'。只需要变换k'次即可。代码 #include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>#include <vector>using namespace std;int const N = 200 + 10;int n,k,a[N],len[N];char t[N],s[N],ans[N];int main(){while(~scanf("%d",&n) && n){memset(len,0,sizeof(len));for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++){int j = i,cnt = 0;do{cnt++;j = a[j];}while(j != i);len[i] = cnt; //求每一个循环的长度}while(scanf("%d",&k) && k){getchar();gets(t);int l = strlen(t);for(int i=0;i<n;i++){if(i < l)s[i] = t[i];elses[i] = ' ';}for(int i=1;i<=n;i++){int p = k % len[i],pos = i;for(int j=1;j<=p;j++)pos = a[pos];ans[pos-1] = s[i-1];}ans[n] = '';printf("%sn",ans);}printf("n");}return 0;} UVA10294 题解 关于旋转变化。每次可以旋转i = 0,1,2……n-1。对于每一个i，旋转产生的循环个数为gcd(n,i)，t种颜色，不动点个数为t^gcd(n,i)。所以等价类为(∑t^gcd(n,i)) / n。关于对称变化，如果n为奇数，那么有n条对称轴。每条对称轴产生n/2个长度为2的循环和一个长度为1的循环，不动点个数为t^(n/2+1)。所以总共的等价类为(n * t^(n/2+1)) / n。如果n为偶数，有n条对称轴，其中n/2条经过一个点和一条边，和奇数情况一样。另外一种是经过两个顶点，产生n/2个长度为2的循环。预处理t的阶乘。代码 #include <bits/stdc++.h>using namespace std;int const N = 50 + 5;typedef long long ll;ll p[N];int n,t;int main(){while(~scanf("%d%d",&n,&t)){p[0] = 1;for(int i=1;i<N;i++)p[i] = p[i-1] * t; //表示t^i/*旋转*/ll a = 0,b = 0,c = 0;for(int i=0;i<n;i++)a += p[__gcd(i,n)];a /= n;/*翻转奇数*/b = n * p[n/2+1];b /= n;/*翻转偶数*/c = (n/2) * p[n/2] + (n/2) * p[n/2+1];c /= n;if(n & 1)printf("%lld %lldn",a,(a + b)/2);elseprintf("%lld %lldn",a,(a + c)/2); //a有n种，c有n种，再除以2}return 0;} UVA11077 题意：给定n和k，统计有多少的排列至少需要交换k次才能变成{1,2,3……，n} 题解 对于一个循环长度为len，至少需要交换len-1次。所以循环的个数为x，所以至少需要交换（n-x）次。dp[i][j]表示有多少个长度为i的排列至少需要交换j次才能变成{1,2,……i}。初始化dp[1][0] = 1,dp[1][j] = 0 (j!=1)。状态转移为dp[i][j] = dp[i-1][j] + dp[i-1][j-1] * (i - 1)。前者表示i单独一个循环，所以不改变交换此时。后者表示插入到前面的任意一个位置，有i-1种情况。比如1->2->3->1，插入x。有1->x->2->3->1,1->2->x->3->1,1->2->3->x->1最后答案为dp[n][k] 代码 #include <bits/stdc++.h>using namespace std;typedef unsigned long long ll;int const N = 30;int n,k;ll dp[N][N];int main(){dp[1][0] = 1;for(int i=2;i<N;i++)for(int j=0;j<i;j++){ //长度为i最多交换i-1次dp[i][j] = dp[i-1][j];if(j > 0)dp[i][j] += dp[i-1][j-1] * (i - 1);}while(~scanf("%d%d",&n,&k) && n || k)printf("%llun",dp[n][k]);return 0;} POJ3270 题意：每次交换都会产生一定代价，求代价最小 题解 交换和上面一样使用置换群，首先要离散化。为使代价最小，有两种策略。1、一个循环都与内部最小的交换，需要交换len-1次。2、一个循环都与整体的最小值交换，需要len次。代码 #include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>#include <vector>using namespace std;int const inf = 0x7f7f7f7f;int const N = 10000 + 10;int a[N],b[N],c[N],n,ans,vis[N],minx;vector<int>v;int main(){scanf("%d",&n);minx = inf;for(int i=1;i<=n;i++){scanf("%d",&a[i]);minx = min(minx,a[i]);v.push_back(a[i]);}sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());for(int i=1;i<=n;i++){int k = lower_bound(v.begin(),v.end(),a[i]) - v.begin();b[i] = k + 1;}for(int i=1;i<=n;i++){if(vis[i])continue;int j = i,s = 0,mx = inf,cnt = 0;do{s += a[j];cnt++;vis[j] = true;mx = min(mx,a[j]);j = b[j];}while(i != j);ans = ans + min((s - mx) + mx * (cnt - 1),s + minx * cnt + mx + minx);}printf("%dn",ans);return 0;} HDU5495 题意：最长公共序列 题解 对于序列ai和bi，来一个映射mp[a[i]] = b[i]。结果就是每个循环的长度减1，再求和。注意循环长度为1的时候不用减1。原理很简单，举例子题目中的 1 5 3 2 6 43 6 2 4 5 1 变换一下 1 3 2 4 5 63 2 4 1 6 5 一目了然代码 #include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>#include <vector>using namespace std;int const N = 100000 + 10;int n,mp[N],a[N],b[N];bool vis[N];int main(){int T;scanf("%d",&T);while(T--){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++)scanf("%d",&b[i]);for(int i=1;i<=n;i++)mp[a[i]] = b[i];int ans = 0;memset(vis,false,sizeof(vis));for(int i=1;i<=n;i++){if(vis[i])continue;int j = i,cnt = 0;do{cnt++;vis[j] = true;j = mp[j];}while(j != i);if(cnt == 1)ans += cnt;else ans += cnt - 1;}printf("%dn",ans);}return 0;} LA3641 题解 n为偶数，平方后分解成两个长度相同的循环。n为奇数，不会分解。所以一个置换能否开方，只要判断偶数的循环能否成对即可。代码 #include <bits/stdc++.h>using namespace std;int const N = 30;char s[N],cnt[N];bool vis[N];int main(){int T;scanf("%d",&T);while(T--){scanf(" %s",s);memset(vis,false,sizeof(vis));memset(cnt,0,sizeof(cnt));for(int i=0;i<26;i++){if(vis[i])continue;int j = i;int n = 0;do{vis[j] = true;j = s[j] - 'A';n++;}while(j != i);cnt[n]++;}bool flag = true;for(int i=2;i<26;i+=2)if(cnt[i] % 2)flag = false;if(flag)printf("Yesn");elseprintf("Non");}return 0;} POJ1721 题意：n为奇数，p经过s次开方运算的得到q。已知q，求p。 题解 一定存在循环，可以暴力去找。或者利用结论，当gcd(n,k)互质，当k%n = 0，T^k = e。所以当k%n = 1,T^k = T。因为一次洗牌是平方，所以我们设洗牌x次变为本身，即2^x次置换。那么x满足2^x % n = 1。代码 #include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>#include <vector>using namespace std;int const N = 1000 + 10;int n,s,a[N],b[2][N],cnt;int main(){scanf("%d%d",&n,&s);for(int i=1;i<=n;i++)scanf("%d",&a[i]);int len = 1,p = 2;if(n != 1){while(1){if(p % n == 1)break;len++;p = p * 2 % n;}}elselen = 0; //xint tmp;if(len)tmp = len - s % len;elsetmp = len;cnt = 0;for(int i=1;i<=n;i++)b[cnt][i] = a[i];for(int i=1;i<=tmp;i++){ //滚动数组cnt ^= 1;for(int i=1;i<=n;i++)b[cnt][i] = b[cnt^1][b[cnt^1][i]];}for(int i=1;i<=n;i++)printf("%dn",b[cnt][i]);return 0;} CF612E 题意：判断置换能否开方，并且求出一种开方结果。 题解 首先判断能否开方，和LA3641的思路是一样。然后麻烦的是合并。对于奇数的循环，可以内部合并，因为它不会分解。对于（1 3 5 7）开方就是（1 5 3 7）每次向前移动2步。对于偶数的循环，可以两两合并。比如（1 2）（3 4）可以合成为（1 3 2 4）。具体见代码。代码 #include <bits/stdc++.h>using namespace std;int const N = 1e6+ 10;int n,a[N],ans[N];bool vis[N];vector<int>bucket[N],b[N];int main(){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++){ //第一遍统计循环的个数if(vis[i])continue;int j = i,cnt = 0;do{vis[j] = true;cnt++;b[i].push_back(j);j = a[j];}while(i != j);bucket[cnt].push_back(i); }for(int i=2;i<=n;i+=2){if(bucket[i].size() & 1){printf("-1n");return 0;}}memset(vis,false,sizeof(vis));for(int i=0;i<bucket[1].size();i++)ans[bucket[1][i]] = bucket[1][i]; //单独处理for(int i=2;i<=n;i++){ //枚举循环的大小for(int j=0;j<bucket[i].size();j++){ //枚举每一个循环if(i & 1){int x = b[bucket[i][j]][0],y = b[bucket[i][j]][i/2+1];while(!vis[x]){vis[x] = vis[y] = true;ans[x] = y;x = a[x];ans[y] = x;y = a[y];}}else{ int x = b[bucket[i][j]][0],y = b[bucket[i][j+1]][0]; //两个不同的循环交叉while(!vis[x] && !vis[y]){vis[x] = vis[y] = true;ans[x] = y;x = a[x];ans[y] = x;y = a[y];}j++;}}}for(int i=1;i<=n;i++)printf("%d%c",ans[i],i != n ? ' ' : 'n');return 0;} POJ2369 题解 一个循环经过T^k = e，k为循环长度。所以只需要求出所有长度的最小公倍数即可。代码 #include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>#include <vector>using namespace std;int const N = 1000 + 10;int n,a[N],ans;bool vis[N];int lcm(int a,int b){return a / __gcd(a,b) * b;}int main(){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);ans = 1;for(int i=1;i<=n;i++){if(vis[i])continue;int j = i,cnt = 0;do{cnt++;vis[j] = true;j = a[j];}while(i != j);ans = lcm(ans,cnt);}printf("%dn",ans);return 0;}