放牧代码和思想
专注自然语言处理、机器学习算法

POJ 1286 Necklace of Beads 题解《挑战程序设计竞赛》

目录

POJ 1286 Necklace of Beads 

许愿珠:用红蓝绿三色共n个珠子串成项链,求旋转和翻转后仍不一样的串法种数?

4.1更加复杂的数学问题 

计数 

虽然是裸的Pólya定理,但属于组合数学的内容,还是少不了自我扫盲。Pólya定理的基础Burnside引理是求解互异的组合状态的个数的方法:

据说该定理的应用比较麻烦,染色问题常用Pólya定理:

其中G={a1 ,…ag}   c(ai )为置换gi的循环节数(i=1…s) 。

对应题目的翻转问题,分奇偶讨论。

奇数时,如题图右,对称轴是一个珠子到圆心的连线,一共n条。选定对称轴后,对称轴上的一个珠子构成一个循环,其他n-1个珠子分别以对称轴对称构成(n-1)/2个循环,所以循环节的个数是 1 + (n – 1) / 2 = (n + 1) / 2 。

偶数时,如题图左,对称轴可能是两个珠子的连线,一共 n / 2条。选定对称轴后,对称轴上的两个珠子构成两个循环,其他n-2个珠子分别以对称轴对称构成(n-2)/2个循环;对称轴还可能是两个珠子的中点和圆心的连线,所有珠子两两对称,构成n / 2 个循环。 

对应题目的旋转问题,直接套用现成结论。

一共n个置换,第i个置换的循环节的个数为gcd(n, i)。证明详见P302:

有了循环节,接下来只要将循环节数c作为幂求mc即可。值得注意的是,同时考虑了旋转和翻转后,置换群的个数应当是2n。

第一种方法直接暴力枚举k:

#include <iostream>
using namespace std;

#define LL long long

int gcd(int a, int b)
{
	return b == 0 ? a : gcd(b, a % b);
}

LL power(LL p, LL n)
{
	LL sum = 1;
	while (n)
	{
		if (n & 1)
			sum *= p;
		p *= p;
		n /= 2;

	}
	return sum;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int n; const LL m = 3;
	while (~scanf("%d", &n) && n != -1)
	{
		if (n == 0)
		{
			puts("0");
			continue;
		}
		LL count = 0;
		for (int i = 1; i <= n; ++i)
			count += power(m, gcd(i, n));
		if (n & 1)
			count += n * power(m, n / 2 + 1);
		else
			count += n / 2 * (power(m, n / 2 + 1) + power(m, n / 2));
		count /= n * 2;
		printf("%lld\n", count);
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////
14463727 hankcs 1286 Accepted 132K 0MS C++ 963B 2015-07-23 22:03:36

第二种方法将相同的gcd合并在一起计算:

#include <iostream>
#include <map>
#include <vector>
using namespace std;

#define LL long long

inline LL power(LL p, LL n)
{
	LL sum = 1;
	while (n)
	{
		if (n & 1)
			sum *= p;
		p *= p;
		n /= 2;
	}
	return sum;
}

//************************************
// Method:    divisor
// FullName:  divisor
// Access:    public 
// Returns:   vector<int> 约数
// Qualifier: 约数枚举
// Parameter: const int & n 目标数n
//************************************
vector<int> divisor(const int& n)
{
	vector<int> res;
	for (int i = 1; i * i <= n; ++i)
	{
		if (n % i == 0)
		{
			res.push_back(i);
			if (i != n / i)
			{
				res.push_back(n / i);
			}
		}
	}

	return res;
}

//************************************
// Method:    prime_factor
// FullName:  prime_factor
// Access:    public 
// Returns:   map<int, int>
// Qualifier: 整数分解
// Parameter: int n
//************************************
map<int, int> prime_factor(int n)
{
	map<int, int> res;
	for (int i = 2; i * i <= n; ++i)
	{
		while (n % i == 0)
		{
			++res[i];
			n /= i;
		}
	}
	if (n != 1)
	{
		res[n] = 1;
	}
	return res;
}

LL polya(const int& m, const int& n)
{
	map<int, int> primes = prime_factor(n);
	vector<int> divs = divisor(n);
	LL res = 0;
	for (int i = 0; i < divs.size(); ++i)
	{
		// 求divs[i]的欧拉函数值
		LL euler = divs[i];
		for (map<int, int>::iterator it = primes.begin(); it != primes.end(); ++it)
		{
			int p = it->first;
			if (divs[i] % p == 0) euler = euler / p * (p - 1);
		}

		res += euler * power(m, n / divs[i]);
	}

	// 最后除以n
	res /= n;
	return res;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int n; const LL m = 3;
	while (~scanf("%d", &n) && n != -1)
	{
		if (n == 0)
		{
			puts("0");
			continue;
		}

		LL count = polya(m, n) * n;
		if (n & 1)
			count += n * power(m, n / 2 + 1);
		else
			count += (power(m, n / 2 + 1) + power(m, n / 2)) * (n / 2);
		count /= 2 * n;
		printf("%lld\n", count);
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////
14463721 hankcs 1286 Accepted 148K 0MS C++ 2202B 2015-07-23 22:01:40

似乎题目的数据量并不大,没有区分度。

Reference

第14-15讲_Burnside引理与Polya定理

ACM组合数学知识.zip

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » POJ 1286 Necklace of Beads 题解《挑战程序设计竞赛》

分享到:更多 ()

评论 1

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    程序设计

    jack2年前 (2015-08-05)回复

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机