Tag Archives: 置换群

HDOJ 5392-Infoplane in Tina Town

HDOJ 5392-Infoplane in Tina Town
Infoplane in Tina Town
Time Limit: 14000/7000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 1636 Accepted Submission(s): 385
Problem Description
There is a big stone with smooth surface in Tina Town. When people go towards it, the stone surface will be lighted and show its usage. This stone was a legacy and also the center of Tina Town’s calculation and control system. also, it can display events in Tina Town and contents that pedestrians are interested in, and it can be used as public computer. It makes people’s life more convenient (especially for who forget to take a device).
Tina and Town were playing a game on this stone. First, a permutation of numbers from 1 to n were displayed on the stone. Town exchanged some numbers randomly and Town recorded this process by macros. Town asked Tine,”Do you know how many times it need to turn these numbers into the original permutation by executing this macro? Tina didn’t know the answer so she asked you to find out the answer for her.
Since the answer may be very large, you only need to output the answer modulo 3∗230+1=3221225473 (a prime).
Input
The first line is an integer T representing the number of test cases. T≤5
For each test case, the first line is an integer n representing the length of permutation. n≤3∗106
The second line contains n integers representing a permutation A1...An. It is guaranteed that numbers are different each other and all Ai satisfies ( 1≤Ai≤n ).
Output
For each test case, print a number ans representing the answer.
Sample Input
2
3
1 3 2
6
2 3 4 5 6 1
Sample Output
2
6
Source
BestCoder Round #51 (div.2)
Recommend
hujie | We have carefully selected several similar problems for you: 5395 5394 5393 5390 5389


此题和POJ 2369-Permutations类似,只是测试样例更多,数据规模更大,最后还要对某个大数取模。所以在求所有循环节长度的最小公倍数的时候,不能使用gcd转换的方法,需要先后使用因式分解和快速幂算法。
参考下面的例子理解分解质因数法求最小公倍数的方法。
60=2×2×3×5
18=2×3×3
lcm(60,18)=180=2×2×3×3×5
通过观察可以看出规律,要求a,b的最小公倍数,先将a和b分解成质因数相乘的形式,对于每一个质因子x,取x在a和b中出现频率最高的数作为x在最小公倍数中的频率。比如2在60中出现2次,但在18中只出现1次,所以2在最小公倍数180中也出现2次,同理质因子3和5分别出现2次和1次。
假设某个质因子x出现y次,则最后要计算x^ymodp,可以使用快速幂方法提高速度,该方法很好理解,将y看成二进制形式,如果y为偶数,则x^y=(x*x)^{y/2};如果y为奇数,则x^y=x*x^{y-1},y-1就是偶数了。同时modp就是快速幂取模了。
完整代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef unsigned long long ULL;
const int kMaxN = 3000005, kNumPrime = 269;
const ULL kMod = 3221225473;
bool visited[kMaxN];
int permutation[kMaxN];
int prime[kNumPrime] = { 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, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723 };
int prime_times[kMaxN];
//求x的所有质因子及其频率
void GetPrimeFactor(int x)
{
	for (int i = 0; i < kNumPrime; i++)
	{
		int tmp = 0;
		while (x%prime[i] == 0)
		{
			tmp++;
			x /= prime[i];
		}
		if (tmp > prime_times[prime[i]])
			prime_times[prime[i]] = tmp;
		if (x == 1)
			return;
	}
	prime_times[x]++;
}
//快速幂取模x^ymod(kMod)
ULL QuickPow(ULL x, ULL y)
{
	ULL ans = 1;
	while (y)
	{
		if (y & 1)
			ans = (ans*x)%kMod;
		x = (x*x) % kMod;
		y >>= 1;
	}
	return ans;
}
int main()
{
	int t, n, len;
	ULL ans;
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d", &n);
		memset(visited, false, kMaxN);
		memset(prime_times, 0, kMaxN);
		for (int i = 1; i <= n; i++)
			scanf("%d", &permutation[i]);
		for (int i = 1; i <= n; i++)
		{
			if (!visited[i])
			{
				visited[i] = true;
				int j = permutation[i];
				len = 1;
				while (j != i)
				{
					visited[j] = true;
					j = permutation[j];
					len++;
				}
				GetPrimeFactor(len);
			}
		}
		ans = 1;
		for (int i = 2; i < n; i++)
			if (prime_times[i] != 0)
				ans = (ans*QuickPow(i, prime_times[i])) % kMod;
		printf("%I64un", ans);
	}
	return 0;
}

本代码提交AC,用时5101MS,内存27984K。

POJ 2369-Permutations

POJ 2369-Permutations
Permutations
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 2792 Accepted: 1473
Description
We remind that the permutation of some final set is a one-to-one mapping of the set onto itself. Less formally, that is a way to reorder elements of the set. For example, one can define a permutation of the set {1,2,3,4,5} as follows:

This record defines a permutation P as follows: P(1) = 4, P(2) = 1, P(3) = 5, etc.
What is the value of the expression P(P(1))? It’s clear, that P(P(1)) = P(4) = 2. And P(P(3)) = P(5) = 3. One can easily see that if P(n) is a permutation then P(P(n)) is a permutation as well. In our example (believe us)

It is natural to denote this permutation by P2(n) = P(P(n)). In a general form the defenition is as follows: P(n) = P1(n), Pk(n) = P(Pk-1(n)). Among the permutations there is a very important one — that moves nothing:

It is clear that for every k the following relation is satisfied: (EN)k = EN. The following less trivial statement is correct (we won't prove it here, you may prove it yourself incidentally): Let P(n) be some permutation of an N elements set. Then there exists a natural number k, that Pk = EN. The least natural k such that Pk = EN is called an order of the permutation P.
The problem that your program should solve is formulated now in a very simple manner: "Given a permutation find its order."
Input
In the first line of the standard input an only natural number N (1 <= N <= 1000) is contained, that is a number of elements in the set that is rearranged by this permutation. In the second line there are N natural numbers of the range from 1 up to N, separated by a space, that define a permutation — the numbers P(1), P(2),…, P(N).
Output
You should write an only natural number to the standard output, that is an order of the permutation. You may consider that an answer shouldn't exceed 109.
Sample Input
5
4 1 5 2 3
Sample Output
6
Source
Ural State University Internal Contest October'2000 Junior Session


有一个序列和一个置换T,问对这个序列置换多少次能恢复成原来的序列。这其实就是求置换群T的秩k使得T^k=e,e为单位置换f(x)=x。
在离散数学中有一个定理,k等于T中所有循环节长度的最小公倍数。
比如题中的P(n)有1->4->2->1,则循环节长度就为3,以及3->5->3,循环节长度为2,则最小公倍数为lcm(3,2)=6,即k=6。
设x,y的最小公倍数为lcm(x,y),最大公约数为gcd(x,y),则有gcd(x, y)×lcm(x, y) = xy,挺神奇的,所以求最小公倍数可以转换为求最大公约数。
完整代码如下:

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
using namespace std;
const int kMaxN = 1005;
bool visited[kMaxN];
int permutation[kMaxN];
//最大公约数
int gcd(int x, int y)
{
	int tmp;
	while (y)
	{
		tmp = y;
		y = x % y;
		x = tmp;
	}
	return x;
}
int main()
{
	int n,ans,len;
	while (scanf("%d", &n)!=EOF)
	{
		ans = 1;
		memset(visited, false, n + 1);
		for (int i = 1; i <= n; i++)
			scanf("%d", &permutation[i]);
		for (int i = 1; i <= n; i++)
		{
			if (!visited[i])
			{
				visited[i] = true;
				int j = permutation[i];
				len = 1;
				while (j!=i)
				{
					visited[j] = true;
					j = permutation[j];
					len++;
				}
				ans = len*ans/gcd(ans, len);//gcd(a, b)×lcm(a, b) = ab
			}
		}
		printf("%dn", ans);
	}
	return 0;
}

本代码提交AC,用时0MS,内存136K。