Polya定理
设G={a1,a2,...,a|G|}是N={1,2,...,N}上的置换群,现用m种颜色对这N个点染色,则不同的染色方案数为
S=(m^c1+m^c2+...+m^c|G|)/|G|
证明比较复杂,略
常见置换的循环数
计算置换的循环数,是这一算法的瓶颈.如果能够快速计算出各置换的循环数,就可以大大提高程序的运行效率
旋转:
s个点顺时针(或逆时针)旋转i个位置的置换,循环数为gcd(n,i)
翻转:
s为偶数时,
对称轴不过顶点:循环数为s/2
对称轴过顶点:循环数为s/2+1
n为奇数时,循环数为(s+1)/2
分析：1）.有1，2....s个旋转；ans+=pow(c,gcd(s,i));i=1......s;(s，代表珠子个数）
2）.有s个翻转。
s为偶数时，有n/2个对称轴过顶点，有n/2个对称轴不过顶点；
ans+=(s/2)*pow(c*1.0,s/2.0)+(s/2)*pow(c*1.0,s/2.0+1);
s为奇数时，s*pow(c*1.0,(s+1)/2*1.0);
3）ans=ans/(s+s);
#include<iostream>
#include<cstdio>
#include<math.h>
using namespace std;
int gcd(int x,int y)
{
return y==0?x:gcd(y,x%y);
}
int main()
{
int c,s;
while(cin>>c>>s)
{
int l=0,g=s,i;
if(c==0&&s==0)
break;
for(i=1;i<=s;i++)//Ðýת
{
l+=(int)pow(c*1.0,gcd(s,i)*1.0);
}
if(s%2==1)//·×ª
{
l+=s*pow(c*1.0,(s+1)/2*1.0);
}
else
{
l+=(s/2)*pow(c*1.0,s/2.0)+(s/2)*pow(c*1.0,s/2.0+1);
}
l/=(g+s);
cout<<l<<endl;
}
return 0;
}