Description
Beads of red, blue or green colors are connected together into a circular necklace of n beads ( n < ). If the repetitions that are produced by rotation around the center of the circular necklace or reflection to the axis of symmetry are all neglected, how many different forms of the necklace are there?
Input
The input has several lines, and each line contains the input data n.
- denotes the end of the input file.
Output
The output should contain the output data: Number of different forms, in each line correspondent to the input data.
Sample Input
-
Sample Output
Source
1、题目类型：Polya定理、组合数学、置换群。
2、解题思路：Polya定理：（1）设G是p个对象的一个置换群，用k种颜色突然这p个对象，若一种染色方案在群G的作用下变为另一种方案，则这两个方案当作是同一种方案，这样的不同染色方案数为：
；
（2）置换及循环节数的计算方法:对于有n个位置的手镯，有n种旋转置换和n种翻转置换.
对于旋转置换: c(fi) = gcd(n,i) i为一次转过i颗宝石（ i = 0 时 c=n;）;
对于翻转置换:如果n为偶数：c(f) = n/2 的置换有n/2个;
c(f) = n/2+1 的置换有n/2个;
如果n为奇数：c(f) = n/2+1.
3、注意事项：注意对于翻转置换过程中对于奇偶数情况的区分处理。
相同的gcd合并在一起计算：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<set>
#include<vector>
using namespace std;
#define ll long long
ll pow_mod(ll a,ll i){
if(i==)
return ;
ll t=pow_mod(a,i/);
ll ans=t*t;
if(i&)
ans=ans*a;
return ans;
} vector<ll> divisor(ll n){
vector<ll> res;
for(ll i=;i*i<=n;i++){
if(n%i==){
res.push_back(i);
if(i*i!=n){
res.push_back(n/i);
}
}
}
return res;
}
ll eular(ll n){
ll res=;
for(ll i=;i*i<=n;i++){
if(n%i==){
n/=i,res*=i-;
while(n%i==){
n/=i;
res*=i;
}
}
}
if(n>) res*=n-;
return res;
}
ll polya(ll m,ll n){
//map<ll,ll> primes = prime_factor(n);
vector<ll> divs = divisor(n);
ll res=;
for(ll i=;i<divs.size();i++){
ll euler=eular(divs[i]);
res+=euler*pow_mod(m,n/divs[i]);
}
res/=n;
return res;
}
int main()
{
ll n,m=;
while(~scanf("%I64d",&n) && n!=-){
if(n==){
puts("");
continue;
}
ll count=polya(m,n)*n;//旋转情况
if(n&){//奇数
count+=n*pow_mod(m,n/+);//翻转情况
}
else{//偶数
count += (pow_mod(m, n / + ) + pow_mod(m, n / )) * (n / );//翻转情况
}
count/=*n;
printf("%I64d\n",count);
}
return ;
}
附上大神代码：
相同的gcd合并在一起计算：
#include <iostream>
#include <map>
#include <vector>
using namespace std; #define LL long long inline LL power(LL p, LL n)
{
LL sum = ;
while (n)
{
if (n & )
sum *= p;
p *= p;
n /= ;
}
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 = ; i * i <= n; ++i)
{
if (n % i == )
{
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 = ; i * i <= n; ++i)
{
while (n % i == )
{
++res[i];
n /= i;
}
}
if (n != )
{
res[n] = ;
}
return res;
} LL polya(const int& m, const int& n)
{
map<int, int> primes = prime_factor(n);
vector<int> divs = divisor(n);
LL res = ;
for (int i = ; 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 == ) euler = euler / p * (p - );
} 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 = ;
while (~scanf("%d", &n) && n != -)
{
if (n == )
{
puts("");
continue;
} LL count = polya(m, n) * n;
if (n & )
count += n * power(m, n / + );
else
count += (power(m, n / + ) + power(m, n / )) * (n / );
count /= * n;
printf("%lld\n", count);
}
#ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
system("out.txt");
#endif
return ;
}
还有一种暴力求法：
#include <iostream>
using namespace std; #define LL long long int gcd(int a, int b)
{
return b == ? a : gcd(b, a % b);
} LL power(LL p, LL n)
{
LL sum = ;
while (n)
{
if (n & )
sum *= p;
p *= p;
n /= ; }
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 = ;
while (~scanf("%d", &n) && n != -)
{
if (n == )
{
puts("");
continue;
}
LL count = ;
for (int i = ; i <= n; ++i)
count += power(m, gcd(i, n));
if (n & )
count += n * power(m, n / + );
else
count += n / * (power(m, n / + ) + power(m, n / ));
count /= n * ;
printf("%lld\n", count);
}
#ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
system("out.txt");
#endif
return ;
}