可以预见数论推公式是有多么蛋疼。

让我简明扼要的讲讲吧(多都说不出来,毕竟才做了两道题)其实呢,这个算法应该归入群论,有个有用的东西:置换群,它表示一个集合包括很多的置换。
先讲讲置换吧:↓(这是个置换)
1 2 3 4
3 1 2 4
怎么个置换法呢?这个就代表,第1个状态置换后变成第3个状态,第2个状态置换后变成第1个状态,第3个状态置换后变成第2个状态,第4个状态置换后变成第4个状态。
然后就是循环节:
1 2 3 4 5
3 5 1 4 2
它等于:(13)(25)(4)
那循环节长度就等于3

嘿嘿,简单吧。

然后就是一个神奇的定理——polya定理,设这个群{g1,g2,……gG}G为置换群的置换数,c(g)表示这个置换的循环节长度,用m种颜色涂点,那不同的涂色方案为:m^c(g1)+m^c(g2)+m^c(gG)的和除以G(这个我实在是证不出来,死记吧),然而c(g)怎么理解?其实这个来源于Burnside引理,我们将其优化变成polya定理,那这个是什么?

burnside引理:用D(i)表示在置换中不变的个数,怎么理解?例如第一个置换,4就是不变的,那这个置换的D就等于1。那不同的涂色方案就等于Σ*D(i)。这个循环节的想法,就是来自于这里的D,同时,由于polya有很大局限性(因为直接用polya题目就太简单啦T>*<T)所以说有很多题都是要用引理+优化。

例题:poj2409

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
LL gcd(LL a,LL b)
{
if(a==)return b;
return gcd(b%a,a);
}
LL power(LL A,LL k)
{
LL ans=;
while(k!=)
{
if(k%==)ans*=A;
A*=A;k/=;
}
return ans;
}
int main()
{
LL n,m;
while(scanf("%lld%lld",&m,&n)!=EOF)
{
if(n==&&m==)break;
LL ans=; for(int i=;i<=n;i++)ans+=power(m,gcd(i,n));
//旋转置换,枚举旋转的豆子个数,置换数为n,循环节长度为LCM(i,n)/i,循环节数为n/(LCM(i,n)/i)=gcd(i,n)
//翻转置换
if(n%==)//假如是奇数,就只有一种情况,n个豆子有n种置换,循环节为(n+1)/2
{
ans+=n*power(m,(n+)/);
}
else//假如是偶数,两种情况,对称轴过豆子或过间隔
{
ans+=n/*power(m,n/);//对称轴过间隔,所有豆子翻转,有n/2种置换,循环节为n/2
ans+=n/*power(m,(n+)/);//对称轴过豆子,两个豆子不变,其他翻转,有n/2种置换,循环节为(n+2)/2
}
printf("%lld\n",ans/(n*));//G=n*2
}
return ;
}
05-13 19:26