置换及其应用专题-白红宇

置换及其应用专题

阅读量：6435 次

发布时间：2019-06-23

本文共 22450 字，大约阅读时间需要 74 分钟。

1、UVa 10294, First Love Part 2

题意：项链和手镯都是由若干珠子穿成的环形饰物，两个手镯翻转之后若相同则视为相同手镯，而项链不会。换句话说，以下两个图，若是手镯则视为相同，项链则视为不同。当然，无论手镯还是项链，旋转之后相同的一定会被视为相同。

给出珠子个数n和珠子颜色数t，求分别可以穿成多少个手镯，多少个项链。

解法：(此题解直接抄的白书，自己不知道怎么叙述- -)等价类计数问题，很裸的Polya定理(Burnside引理)。

　　　一共两种置换，旋转和翻转。为了叙述方便，将所有珠子标为0, 1, 2...n-1。

　　　旋转：如果逆时针旋转i的间距，则珠子0, i, 2i...构成一个循环。这个循环有n / gcd(n, i)个元素(想想)，所以一共有gcd(n, i)个循环。所以，这些循环的不动点总数为a = sum (t^gcd(n, i))(i = 0, 1, 2...n-1)(gcd(n, 0) = n)

　　　翻转：当n为奇数，对称轴只有1种，有n条，所以这些置换的不动点数为b = n * t ^ ((n+1)/2)；

　　　　　　当n为偶数，对称轴有两种，每种种n/2条，不动点总数为b = (n / 2) * (t^(n/2+1) + t^(n/2))；

　　　项链数a / n，手镯数为(a + b) / (2*n)。(Burnside引理)

tag:math, Polya, Burnside, good

1 /* 2  * Author:  Plumrain 3  * Created Time:  2013-09-07 15:33 4  * File Name: (good)-math-UVa-10294.cpp 5  */ 6 #include
      
        7 #include
       
         8  9 using namespace std;10 11 12 typedef long long int64;13 14 int64 Mypow(int64 a, int64 n)15 {16     int64 ret = 1;17     while (n > 0){18         if (n & 1)19             ret *= a;20         n >>= 1;21         a *= a;22     }23     return ret;24 }25 26 int gcd(int a, int b)27 {28     return b == 0 ? a : gcd(b, a%b);29 }30 31 int main()32 {33     int n, t;34     while (scanf ("%d%d", &n, &t) != EOF){35         int64 ans1 = 0;36         for (int i = 0; i < n; ++ i)37             ans1 += Mypow (t, gcd(n, i));38         int64 ans2 = ans1;39         if (n & 1) ans2 += n * Mypow (t, (n+1)/2);40         else ans2 += n * (Mypow (t, n/2) + Mypow (t, n/2+1)) / 2;41         printf ("%lld %lld\n", ans1/n, ans2 / (2*n));42     }43     return 0;44 }

View Code

2、NWERC2006, LA 3641, Leonardo's Notebook

　　POJ 3128 Leonardo's Notebook

题意：给出26个大写字母的一个置换B，问是否存在一个置换A，使得A*A = B。(两道题是一样的)

解法：举例来看一下A^2的运算。A = (a1 a2 a3)(b1 b2 b3 b4)，则A^2 = (a1 a2 a3)(a1 a2 a3)(b1 b2 b3 b4)(b1 b2 b3 b4)。而(a1 a2 a3)(a1 a2 a3) = (a1 a3 a2)，(b1 b2 b3 b4)(b1 b2 b3 b4) = (b1 b3)(b2 b4)。总结规律得到，两个长度为n的相同循环相乘，当n为奇数时结果也是一个长度为n的循环B，当n为偶数时结果分裂为两个长度为n/2的不相交的循环相乘。

　　　所以，可以将置换B分解成多个不相交的循环，分别考虑每个循环即可。对于某个循环，若它的长度n为奇数，则在A中一定可以构造出一个循环使得其乘积为B中循环；若长度n为偶数，要求A中存在一个2*n的循环即可，即B中长度为n的循环的个数为偶数，否则不存在A使A*A=B。

tag:math, permutation, think, good

1 /* 2  * Author:  Plumrain 3  * Created Time:  2013-09-07 18:43 4  * File Name: math-NWERC2006-LA3641.cpp 5  */ 6 #include 
      
        7 #include 
       
         8 #include 
        
          9 #include 
         
          10 #include 
          
           11 #include 
           12 13 using namespace std;14 15 #define PB push_back16 17 map
            
              mp;18 vector
             
               ans;19 20 void init()21 {22 string s;23 s.clear();24 cin >> s;25 mp.clear();26 for (int j = 'A'; j <= 'Z'; ++ j)27 mp[j-'A'] = s[j-'A'] - 'A';28 }29 30 bool gao()31 {32 ans.clear();33 for (int i = 0; i < 26; ++ i){34 if (mp[i] == -1 || mp[i] == i) continue;35 36 int tmp = mp[i], cnt = 1;37 mp[i] = -1;38 while (mp[tmp] != -1){39 cnt ++;40 int x = tmp;41 tmp = mp[tmp];42 mp[x] = -1;43 }44 if (!(cnt & 1)) ans.PB (cnt);45 }46 47 sort (ans.begin(), ans.end());48 if (ans.size () & 1) return false;49 for (int i = 0; i < ans.size(); i += 2)50 if (ans[i] != ans[i+1]) return false;51 return true;52 }53 54 int main()55 {56 int T;57 scanf ("%d", &T);58 while (T--){59 init ();60 61 if (gao()) printf ("Yes\n");62 else printf ("No\n");63 }64 return 0;65 }

View Code

3、UVa 11077, Find the Permutations

题意：给出一个{1, 2, 3, ..., n}的一个排列，可以通过一系列的交换变成{1, 2, 3, ..., n}。比如{1, 2, 4, 3}需要1次改变变为{1, 2, 3, 4}，{1, 4, 3, 2}需要2次，{1, 2, 3, 4}需要0次。给定n，k，求有多少个排列至少需要k次交换才能变成{1, 2, ..., n}。

解法：首先，用置换的角度来考虑。设任意一个排列P，将他变为{1...n}的变化过程记为置换A，置换A中含有若干个循环(循环之间不会影响交换次数)，对某个循环若为(a1, a2, a3...ak)，则该循环内交换次数需要交换k-1次，所有循环需要交换次数之和即为P的交换次数。比如，如果A = (a1, a2, a4)a3(a5, a6)，则需要2 + 0 + 1次交换。

　　　分析到这里，已经不难看出问题变成了一个递推问题了，但这道题的递推算是比较难推的了- -。用f(i, j)表示至少需要j次交换才能变成{1, 2...i}，则f(i, j) = f(i-1, j) + f(i-1, j-1) * (i-1)，因为对于元素i，它要么形成自己单独的循环，要么加入任意一个循环的任意一个位置(所有循环共i-1个位置)。边界f(1,1) = f(1, j) = 0，f(i, 0) = 0。

tag:math, permutation, 递推, good

1 /* 2  * Author:  Plumrain 3  * Created Time:  2013-09-09 00:02 4  * File Name: math-UVa-11077.cpp 5  */ 6 #include
      
        7 #include
       
         8 #include
        
          9 10 using namespace std;11 12 #define CLR(x) memset(x, 0, sizeof(x))13 14 typedef unsigned long long int64;15 16 const int N = 21;17 int64 f[N+1][N+1];18 19 int64 gao(int64 n, int64 k)20 {21     int64& x = f[n][k];22     if (x != -1) return x; 23     if (n == 1 && k == 1) return 0;24     if (k == 0) return 1;25     if (n == 1) return 0;26     27     x = gao(n-1, k-1) * (n-1) + gao(n-1, k);28     return x;29 }30 31 int main()32 {33     int n, k;34     for (int i = 0; i <= N; ++ i)35         for (int j = 0; j <= N; ++ j)36             f[i][j] = -1;37     while (scanf ("%d%d", &n, &k) != EOF && !(!n && !k)){38         printf ("%llu\n", gao(n, k));39     }40     return 0;41 }

View Code

4、POJ 1286 Necklace of Beads

5、POJ 2409 Let it Bead

它们都为UVa 10294, First Love Part 2(本篇文章第一题)的简略版，只需要求颜色为t的情况下手镯的数量。

Ps:比较坑的是，POJ1286n可能为0，且为0时应该输出0，这两点分别导致我RE一次，WA一次- -

tag:math, Polya, Burnside

1 /* 2  * Author:  Plumrain 3  * Created Time:  2013-09-30 21:18 4  * File Name: math-POJ-1286.cpp 5  */ 6 #include
      
        7 #include
       
         8 #include
        
          9 #include
         
          10 11 using namespace std;12 13 #define CLR(x) memset(x, 0, sizeof(x))14 15 typedef long long int64;16 17 int64 pow3[30];18 19 int gcd(int a, int b)20 {21     return b == 0 ? a : gcd(b, a%b);22 }23 24 int64 gao(int64 n)25 {26     int64 ret = 0;27     for (int i = 0; i < n; ++ i)28         ret += pow3[gcd(i, n)];29 30     if (n&1)31         ret += n * pow3[n/2+1];32     else33         ret += (pow3[n/2] + pow3[n/2+1]) * (n/2);34     ret /= 2 * n;35     return ret;36 }37 38 int main()39 {40     int n;41     CLR (pow3);42     pow3[0] = 1;43     for (int i = 1; i < 24; ++ i)44         pow3[i] = pow3[i-1] * 3;45 46     while (scanf ("%d", &n) != EOF && n != -1){47         if (!n) printf ("0\n");48         else printf ("%lld\n", gao((int64)n));     49     }50     return 0;51 }

View Code

1 /* 2  * Author:  Plumrain 3  * Created Time:  2013-10-01 14:05 4  * File Name: math-POJ-2409.cpp 5  */ 6 #include
      
        7 #include
       
         8 #include
        
          9 10 using namespace std;11 12 #define CLR(x) memset(x, 0, sizeof(x))13 14 typedef long long int64;15 16 int64 pow[40];17 18 int gcd(int a, int b)19 {20     return b == 0 ? a : gcd(b, a%b);21 }22 23 int main()24 {25     int64 c, n;26     while (scanf ("%lld%lld", &c, &n) != EOF && n){27         CLR (pow);28         pow[0] = 1;29         for (int i = 1; i <= n; ++ i)30             pow[i] = pow[i-1] * c;31         int64 ans = 0;32         for (int i = 0; i < n; ++ i)33             ans += pow[gcd(i, n)];34         if (n & 1)35             ans += n * pow[n/2+1];36         else37             ans += (pow[n/2] + pow[n/2+1]) * (n/2);38         ans = ans / 2 / n;39         printf ("%lld\n", ans);40     }41     return 0;42 }

View Code

6、POJ 3270 Cow Sorting

题意：现在有n个物品分别标号为0～n-1，他们的重量分别是a[i]。现在，要将他们按照重量大小递增的顺序重新排列。每次只能交换两件物品的位置，并且消耗时间为两件物品重量之和。问最短用多少时间能将重新排序完成。

解法：这道题本质就是一个置换，它里面含有许多循环。

　　　在不考虑消耗时间多少的情况下，只需要每个循环内部互相换位置，就能完成递增的重新排列。此时，耗时最小的情况是，用重量最小的物品与所有物品换位置。对某个循环，记其所含元素个数为cnt，所有元素中重量最小的一个重量mi，所有元素重量和为sum，此种情况所需时间最少为tmp1 = cnt == 1 ? 0 : ((cnt-2)*mi + sum)。

　　　当然，还有另外一种换位置的方法，就是对某个循环，将该循环外的一个物品引入循环。这种方法耗时最小的情况是，用所有物品中重量最小的物品与循环内所有物品交换位置。设所有物品中重量最小的为all_min，则tmp2 = sum + mi + (cnt+1) * all_min。

　　　所以对每个循环，ans += min (tmp1, tmp2)。

　　　其实，只要考虑到最优解可能有两种换位置方法，在手算模拟一下，很容易就能得出以上结论。

tag: math, permutation, think

1 /* 2  * Author:  Plumrain 3  * Created Time:  2013-10-01 18:49 4  * File Name: math-POJ-3270.cpp 5  */ 6 #include
      
        7 #include
       
         8 #include
        
          9 #include
         
          10 #include
          
           11 #include
           
            12 13 using namespace std;14 15 #define CLR(x) memset(x, 0, sizeof(x))16 #define PB push_back17 18 const int maxint = 2147483647;19 const int N = 10000;20 21 typedef long long int64;22 23 bool fla[N+5];24 int pat[N+5];25 int64 all_min;26 vector
            
             
               > num;27 28 int64 min(int64 a, int64 b)29 {30 return a < b ? a : b;31 }32 33 int64 gao(int64 n)34 {35 CLR (fla);36 int64 ret = 0;37 for (int i = 0; i < n; ++ i) if (!fla[i]){38 int64 mi = maxint, sum = 0;39 int cnt = 0, pos = i;40 while (!fla[pos]){ 41 ++ cnt; sum += num[pos].first;42 mi = min(mi, num[pos].first);43 fla[pos] = 1;44 pos = pat[pos];45 }46 if (cnt >= 2){47 int64 tmp = (int64)(cnt-2) * mi + sum;48 tmp = min(sum + (int64)(cnt+1) * all_min + mi, tmp);49 ret += tmp;50 }51 }52 return ret;53 }54 55 bool cmp(pair
              
                a, pair
               
                 b)56 {57 return a.first < b.first;58 }59 60 int main()61 {62 int64 n;63 while (scanf ("%lld", &n) != EOF){64 int64 tmp;65 num.clear();66 for (int i = 0; i < n; ++ i){67 scanf ("%lld", &tmp);68 pair
                
                  p = make_pair(tmp, i);69 num.PB(p);70 }71 72 sort(num.begin(), num.end(), cmp);73 all_min = num[0].first;74 CLR (pat);75 for (int i = 0; i < n; ++ i)76 pat[i] = num[i].second;77 78 printf ("%lld\n", gao(n));79 }80 return 0;81 }

View Code

7、POJ 1026 Cipher　　

题意：给你一个长为n的字符串s[i]，和一个置换a[i]。每次操作为：s[a[i]] = s[i]。求进行k次操作以后的字符串。

解法：很简单的置换问题。水题

tag:math, permutation

1 /* 2  * Author:  Plumrain 3  * Created Time:  2013-10-04 11:41 4  * File Name: math-POJ-1026.cpp 5  */ 6 #include
      
        7 #include
       
         8 #include
        
          9 #include
         
          10 11 using namespace std;12 13 #define CLR(x) memset(x, 0, sizeof(x))14 #define PB push_back15 16 const int N = 200;17 18 typedef vector
          
            VI;19 20 int n;21 int a[N+5], tmp[N+5];22 bool fla[N+5];23 24 void gao(int m)25 {26     CLR (fla); CLR (tmp);27     VI cur;28     for (int i = 0; i < n; ++ i) if (!fla[i]){29         cur.clear();30         int pos = i;31         while (!fla[pos]){32             fla[pos] = 1;33             cur.PB (pos);34             pos = a[pos];35         }36         int sz = cur.size();37         for (int i = 0; i < sz; ++ i)38             tmp[cur[(i+m)%sz]] = cur[i];39     }40 41     char s[N+5], c;42     int len = 0;43     CLR (s);44     scanf ("%c", &c);45     while (scanf ("%c", &c) != EOF && c != '\n')46         s[len++] = c;47     while (len < n) s[len++] = ' ';48     for (int i = 0; i < n; ++ i)49         printf ("%c", s[tmp[i]]);50     printf ("\n");51 }52 53 int main()54 {55     while (scanf("%d", &n) != EOF && n){56         for (int i = 0; i < n; ++ i){57             scanf ("%d", &a[i]);58             -- a[i];59         }60 61         int x;62         while (scanf("%d", &x) != EOF && x)63             gao(x);64         printf ("\n");65     }66     return 0;67 }

View Code

8、POJ 2154 Color

题意：用n种颜色将长度为n的项链染色，n种颜色不必用完。项链围绕中心旋转后如果不变则视为相同项链。给定n和p，求项链种数%p。

　　　n <= 10^9，1 <= P <= 30000

解法：首先，肯定是最普通的Polya定理，(∑n ^ gcd(n, i)) / n，其中0 <= i < n。但是存在两个问题，一方面，由于取模p和要除的数n并不一定互质，所以不一定存在逆元，不能将除法变为乘法，而考虑到这道题的特殊性，长度和染色种数一样，所以求∑n ^ (gcd(n, i)-1)即可。另一方面，由于n很大，如果枚举所有的i肯定超时。所以考虑用欧拉定理优化。如果d = gcd(n, i)，则gcd(n/d, i/d) = 1，所以枚举n的所有约数k，则所求为∑(phi[n/k] * n ^ k)。这样，问题就得到了解答。

　　　值得注意的是，这道题时间卡得很紧，所以每一步都要想到最优化的写法，不然可能总体算法对了，但是仍然会TLE- -。

tag:math, permutation, Euler, good

1 /*  2  * Author:  Plumrain  3  * Created Time:  2013-10-18 10:45  4  * File Name: math-POJ-2154.cpp  5  */  6 #include
      
         7 #include
       
          8 #include
        
           9 #include
         
           10 #include
          
            11  12 using namespace std; 13  14 #define CLR(x) memset(x, 0, sizeof(x)) 15 const int N = 1000000; 16  17 int phi[N+5]; 18 int vis[50005], prm[50005]; 19 int mod, nprm; 20  21 void sieve(int n) 22 { 23     int m = (int)sqrt(n+0.5); 24     CLR (vis); 25     for (int i = 2; i <= m; ++ i) if (!vis[i]) 26         for (int j = i*i; j <= n; j += i) vis[j] = 1; 27 } 28  29 int primes(int n) 30 { 31     sieve(n); 32     int ret = 0; 33     for (int i = 2; i <= n; ++ i) 34         if (!vis[i]) prm[ret++] = i; 35     return ret; 36 } 37  38 void phi_table(int n) 39 {  40     CLR (phi); 41     phi[1] = 1; 42     for (int i = 2; i <= n; ++ i) if (!phi[i]){ 43         for (int j = i; j <= n; j += i){ 44             if (!phi[j]) phi[j] = j; 45             phi[j] -= phi[j]/i; 46         } 47     } 48 } 49  50 int euler_phi(int n) 51 {  52     if (n <= N) return phi[n] % mod; 53  54     int m = (int)sqrt(n + 0.5); 55     int ans = n; 56     for (int i = 0; i
           
             1) ans -= ans/n; 62 return ans % mod; 63 } 64 65 int pow_mod(int p, int n) 66 { 67 int ret = 1; 68 p %= mod; 69 while (n > 0){ 70 if (n & 1) ret = (ret * p) % mod; 71 n >>= 1; 72 p = (p * p) % mod; 73 } 74 return ret; 75 } 76 77 int Polya(int n) 78 { 79 int ret = 0; 80 for (int i = 1; i*i <= n; ++ i) if (n % i == 0){ 81 ret = (ret + pow_mod(n, n/i-1) * euler_phi(i)) % mod; 82 if (i*i < n) 83 ret = (ret + (pow_mod(n, i-1) % mod) * (euler_phi(n/i) % mod)) % mod; 84 } 85 if (ret < 0) ret += mod; 86 return ret; 87 } 88 89 int main() 90 { 91 phi_table(N); 92 nprm = primes(50000); 93 int T, n; 94 scanf ("%d", &T); 95 while (T--){ 96 scanf ("%d%d", &n, &mod); 97 printf ("%d\n", Polya(n)); 98 } 99 return 0;100 }

View Code

9、POJ 2888 Magic Bracelet

题意：用m种颜色的珠子串长度为n的项链，有颜色相邻限制，即对每种颜色，它不能和某些颜色的珠子相邻。若旋转相同则视为同一种项链。求这样的项链数量mod 9973。

　　　1 ≤ n ≤ 10^{9，1 ≤ m ≤ 10}

解法：首先，若没有颜色相邻限制，则就可以用burnside引理轻易解决。对于颜色限制，就相当于解决这个问题，设f(x)是长度为x且该链的第一颗珠子和最后一颗珠子可以相领的链有多少种。求f(x)可以考虑递推，但是由于n可能为10^9，所以无论时间还是空间复杂度都无法接受。所以可以用矩阵来解决这个问题。设I为表示颜色是否可以相邻的矩阵(可相邻记为1)，则f(x)为 I^(x+1)的主对角线元素之和。

tag:math, Polya, 矩阵乘法快速幂, 乘法逆, good

1 /*  2  * Author:  Plumrain  3  * Created Time:  2013-10-17 18:26  4  * File Name: math-POJ-2888.cpp  5  */  6 #include
      
         7 #include
       
          8 #include
        
           9 #include
         
           10  11 using namespace std; 12  13 const int mod = 9973; 14 typedef int matrix[15][15]; 15  16 matrix pat; 17 int n, m, k; 18  19 void init() 20 { 21     scanf ("%d%d%d", &n, &m, &k); 22      23     for (int i = 0; i < m; ++ i) 24         for (int j = 0; j < m; ++ j) 25             pat[i][j] = 1; 26     while (k--){ 27         int ta, tb; 28         scanf ("%d%d", &ta, &tb); 29         -- ta; -- tb; 30         pat[ta][tb] = 0; 31         pat[tb][ta] = 0; 32     } 33 } 34  35 int euler_phi(int n) 36 { 37     int m = (int)sqrt(n + 0.5); 38     int ans = n; 39     for (int i = 2; i <= m; ++ i) 40         if (!(n % i)){ 41             ans = ans / i * (i-1); 42             while (!(n % i)) n /= i; 43         } 44     if (n > 1) ans = ans / n * (n-1); 45     return (ans % mod); 46 } 47  48 void mtx_mul(matrix& A, matrix B) 49 { 50     matrix ret; 51     for (int i = 0; i < m; ++ i) 52         for (int j = 0; j < m; ++ j){ 53             ret[i][j] = 0; 54             for (int k = 0; k < m; ++ k) 55                 ret[i][j] = (ret[i][j] + A[i][k] * B[k][j]) % mod; 56             if (ret[i][j] < 0) ret[i][j] += mod; 57         } 58  59     for (int i = 0; i < m; ++ i) 60         for (int j = 0; j < m; ++ j) 61             A[i][j] = ret[i][j]; 62 } 63  64 void mtx_pow(matrix& A, int n) 65 { 66     -- n; 67     if (!n) return; 68      69     matrix ret; 70     for (int i = 0; i < m; ++ i) 71         for (int j = 0; j < m; ++ j) 72             ret[i][j] = A[i][j]; 73     while (n > 0){ 74         if (n & 1) mtx_mul(ret, A); 75         n >>= 1; 76         mtx_mul(A, A); 77     } 78  79     for (int i = 0; i < m; ++ i) 80         for (int j = 0; j < m; ++ j) 81             A[i][j] = ret[i][j]; 82 } 83  84 int pow_mod(int n, int p) 85 { 86     n %= mod; 87     int ret = 1; 88     while (p > 0){ 89         if (p & 1) ret = (ret * n) % mod; 90         p >>= 1; 91         n = (n * n) % mod; 92     } 93     return ret; 94 } 95  96 int solve(int n) 97 { 98     matrix A; 99     for (int i = 0; i < m; ++ i)100         for (int j = 0; j < m; ++ j)101             A[i][j] = pat[i][j];102     mtx_pow(A, n);103     int ret = 0;104     for (int i = 0; i < m; ++ i)105         ret = (ret + A[i][i]) % mod;106     if (ret < 0) ret += mod;107     return ret;108 }109 110 int Polya()111 {112     int ret = 0;113     for (int i = 1; i*i <= n; ++ i) if (n % i == 0){114         if (i*i < n) ret = (ret + solve(i)*euler_phi(n/i) + solve(n/i)*euler_phi(i)) % mod;115         else ret = (ret + solve(i) * euler_phi(i)) % mod;116     }117     return (ret * pow_mod(n%mod, mod-2)) % mod;118 }119 120 int main()121 {122     int T;123     scanf ("%d", &T);124     while (T--){125         init(); 126         printf ("%d\n", Polya());127     }128     return 0;129 }

View Code

10、POJ 1721 CARDS

题意：定义一种操作double shuffle，对置换a[]，将所有a[i]处的牌变为a[a[i]]。给出一个置换T'进行了m次操作以后的结果，求原置换T。

　　　原置换循环节数为1，长度n <= 1000，且n为奇数，s <= 1000。

解法：在写解法之前，先写一个问题。就是题目并没有告诉原置换循环节数为1，但是通过题面的这句话可以得知“Alice first writes down all the numbers from 1 to N in some random order: a1, a2, ..., aN. Then she arranges the cards so that the position ai holds the card numbered a_i+1, for every 1 <= i <= N-1, while the position aN holds the card numbered a1. ”。因为x[a[0]] = a[1]，x[a[1]] = a[2]，x[a[2]] = a[3]....

　　　两种解法：

　　　法一。这种解法偏向于暴力。首先，对任意循环，总存在一个数k使得T^k = T，首先暴力处理T可以求得k，然后，将T'进行double shuffle操作k - (m%k)次即可。模拟可以通过，32ms。

　　　法二。置换群的开方运算。

　　　首先，要注意到，double shuffle操作即是将置换T变为T^2。其次，注意到置换为单循环且长度n为奇数。所以，置换T在变成T'的过程中并没有发生循环分裂，所以直接用以下公式解决该问题：设数组a[] = T，a'[] = T'，(a[0] = 0)，则a'[i] = a[(i*(2^m)) % n]。(该公式具体参见潘震皓的《置换群快速幂运算研究与探讨》，该文讲得非常好)

tag:math, permutation, 置换群的开方, good

解法1：

1 /* 2  * Author:  Plumrain 3  * Created Time:  2013-10-20 15:09 4  * File Name: math-POJ-1721.cpp 5  */ 6 #include
      
        7 #include
       
         8 #include
        
          9 #include
         
          10 11 using namespace std;12 13 #define CLR(x) memset(x, 0, sizeof(x))14 #define PB push_back15 const int N = 1000;16 typedef vector
          
            VI;17 18 int a[N+5], b[2][N+5];19 20 int gao(int n, int m)21 {22     int k = 0, idx = 0;23     for (int i = 0; i < n; ++ i)24         b[0][i] = a[i]; 25     while (1){26         bool fla = false;27         for (int i = 0; i < n; ++ i)28             b[idx^1][i] = b[idx][b[idx][i]];29         idx ^= 1;30         ++ k;31         for (int i = 0; i < n; ++ i)32             if (b[idx][i] != a[i]) fla = 1;33         if (!fla) break;34     }35 36     m %= k;37     int tim = k - m;38     idx = 0;39     for (int i = 0; i < n; ++ i)40         b[0][i] = a[i];41     while (tim--){42         for (int i = 0; i < n; ++ i)43             b[idx^1][i] = b[idx][b[idx][i]];44         idx ^= 1;45     }46     return idx;47 }48     49 int main()50 {51     int n, m;52     while (scanf ("%d%d", &n, &m) != EOF){53         for (int i = 0; i < n; ++ i){54             scanf ("%d", &a[i]);55             -- a[i];56         }57         int idx = gao(n, m);58         for (int i = 0; i < n; ++ i)59             printf ("%d\n", b[idx][i] + 1);60     }61     return 0;62 }

View Code

解法2：

1 /* 2  * Author:  Plumrain 3  * Created Time:  2013-10-21 15:26 4  * File Name: math-POJ-1721-2.cpp 5  */ 6 #include
      
        7 #include
       
         8 #include
        
          9 10 using namespace std;11 12 #define CLR(x) memset(x, 0, sizeof(x))13 const int N = 1000;14 15 int a[N+5], cir[N+5], ans[N+5], tmp[N+5];16 17 int pow_mod(int p, int n, int mod)18 {19     p %= mod;20     int ret = 1;21     while (n > 0){22         if (n & 1) ret = (ret * p) % mod;23         n >>= 1;24         p = (p * p) % mod;25     }26     return ret;27 }28 29 void gao(int n, int m)30 {31     int pos = 0;32     while (a[pos])33         pos = a[pos];34     cir[0] = pos = 0; 35     int idx = 1;36     while (a[pos]){37         cir[idx++] = a[pos];38         pos = a[pos]; 39     }40     int k = pow_mod(2, m, n);41     for (int i = 0; i < n; ++ i)42         tmp[(i*k)%n] = cir[i];43     for (int i = 0; i < n-1; ++ i)44         ans[tmp[i]] = tmp[i+1];45     ans[tmp[n-1]] = tmp[0];46 }47 48 int main()49 {50     int n, m;51     while (scanf ("%d%d", &n, &m) != EOF){52         for (int i = 0; i < n; ++ i){53             scanf ("%d", &a[i]);54             -- a[i];55         }56         gao(n, m);57         for (int i = 0; i < n; ++ i)58             printf ("%d\n", ans[i] + 1);59     }60     return 0;61 }

View Code

11、POJ 3590 The shuffle Problem

题意：给定一个n，求长度为n的置换，使得它的置换周期最大。输出置换周期，并且输出置换本身。若有置换周期相同的置换，输出字典序小的。

　　　n <= 100

解法：首先，对于一个置换，它的置换周期就是所有循环长度的最小公倍数。那么，这道题就变为求n[i]，使得n[i]之和为n，且n[i]的最小公倍数最大。

　　　用贪心思想：若要在n[i]之和为n的情况下使得他们的最小公倍数最大，则n[i]均为p^t的形式，其中p为质数，t为任意正整数。

　　　这样，生下来的问题就可以用dp解决了。

　　　要注意的是，不能在用贪心思想之前直接这样dp(我是这样WA的)：设dp[i]表示和为i的若干数的最大最小公倍数，dp[i] = max(dp[i], lcm(dp[j], dp[i-j])，j = 1 to i-1。因为虽然”在m > k的情况下，有dp[m] > dp[k]“，但是”在m > k的情况下，lcm(dp[t], dp[m]) > lcm(dp[t], dp[k])“是错误的，所以这种dp方法也是错误的。

tag:math, permutation, dp, greedy

Ps:官方题解：

1 /* 2  * Author:  Plumrain 3  * Created Time:  2013-10-21 23:44 4  * File Name: math-POJ-3590.cpp 5  */ 6 #include
      
        7 #include
       
         8 #include
        
          9 #include
         
          10 #include
          
           11 12 using namespace std;13 14 #define CLR(x) memset(x, 0, sizeof(x))15 #define PB push_back16 const int N = 100;17 typedef vector
           
             VI;18 typedef long long int64;19 20 int64 ans = 0;21 int prm[30] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};22 VI cur, tmp;23 24 void dp(int n, int sum, int l)25 {26 if (l > ans){ 27 ans = l;28 cur = tmp;29 for (int i = 0; i < sum; ++ i)30 cur.PB (1);31 }32 33 for (int i = n+1; prm[i] <= sum; ++ i){34 int xxx = prm[i];35 while (xxx <= sum){36 tmp.PB (xxx);37 dp(i, sum-xxx, xxx*l);38 tmp.pop_back();39 xxx *= prm[i];40 }41 }42 }43 44 int main()45 {46 int T;47 scanf ("%d", &T);48 while (T--){49 int n;50 scanf ("%d", &n);51 52 if (n == 1){53 printf ("1 1\n");54 continue;55 }56 57 cur.clear(); ans = 0;58 for (int i = 0; prm[i] <= n; ++ i){59 int xxx = prm[i];60 while (xxx <= n){61 tmp.clear();62 tmp.PB (xxx);63 dp(i, n-xxx, xxx);64 xxx *= prm[i]; 65 }66 }67 68 int64 mul = 1;69 for (int i = 0; i < cur.size(); ++ i)70 mul *= cur[i];71 printf ("%lld", mul);72 sort(cur.begin(), cur.end());73 int idx = 0;74 for (int i = 0; i < cur.size(); ++ i){75 for (int j = 1; j < cur[i]; ++ j)76 printf (" %d", idx+1+j);77 printf (" %d", idx+1);78 idx += cur[i];79 }80 printf ("\n");81 }82 return 0;83 }