注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Memento

这是一间记忆仓库~~

 
 
 

日志

 
 

Polya定理总结  

2012-03-15 20:56:45|  分类: 学习小结 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
       这是一篇寒假就该写的总结,结果被我拖到的现在。看了《暗时间》,再次意识到写blog是只有好处的一件事,总结解题报告什么的不管别人看没看懂,受益最大的始终是自己。所以决定这几天把寒假到现在学的一些东西,刷的一些题,看的一些书都记录一下,十年之后这些都是宝贵的资料,记录着自己成长的轨迹,比任何的照片都有力。才一个月而已,好多一开始的感悟和理解却都有点模糊,包括最后写的一个自己还算满意的模板也因为硬盘杯具而杯具了,只好重新再来一遍了,就当是复习吧。

       讲Polya最好的资料应该就是Richard A. Brualdi写的《组合数学》,最好是看英文版第四版的。这本数最后一章讲的就是Polya定理,讲的很详细,每一步都有证明,并没有涉及什么高深的群论知识,但学过群论后我发现作者其实是把群论的一些定理都从零推了一遍,DBL。国家集训队的论文里有两篇是讲Polya定理的:2001年——符文杰《Pólya原理及其应用》、2008年——陈瑜希《Pólya计数法的应用》。虽然也有证明过程,但是限于篇幅,肯定没有书讲的细,不过论文上的例题都是好题,看完书后可以用来练手。下面简单的写下推理过程,我试着不看书自己推了一遍,发现很快就推出来了,看来是学了群论以后加深了理解- -

       首先记Sn为有前n个正整数组成的集合,G为Sn的置换群,C为Sn的着色集。那么我们等于是要求C中有多少种着色方案是不等价的。定义两种着色等价的概念:如果对于在C中的两种着色c1、c2,存在置换f使得f*c1=c2,那么c1和c2就是等价的。要想求不等价着色的个数,我们要先证明一个定理,即:

      Burnside定理:设G(c)={f|f属于G,f*c=c},C(f)={c|c属于C,f*c=c}。那么对于每一种着色c,那么与c等价的着色数=|G|/|G(c)|。

      证明:首先可以证明G(c)为Sn的一个置换群。那么对于任意的f*c=g*c,可知f的逆*g属于G(c),所以g={f&h|h属于G(c)}。那么在|g|=|G(c)|。所以与c等价的着色数=|G|/|G(c)|。这样我们就得到了Burnside定理。

      我们现在就用Burnside定理来得到最终的答案。先设N(G,C)为C中不等价的着色数。我们考虑这样一个计数过程:求所有的(f,c)满足f*c=c的总对数。那么我们有:

                                  sum{|G(c)|}(对于每一个c属于C)=sum{|C(f)|}(对于每一个f属于G)。

      由Burnside定理可对等式左边进行替换,得到:

                                  sum{|G|/与c等价的着色数}(对于每一个c属于C)=sum{|C(f)|}(对于每一个f属于G)。

      如果我们把右边的式子展开的话,等价类相互合并和就把分母给消去了,最后得到的就是不等价类的个数:

                                  N(G,C)*|G|=sum{|C(f)|}(对于每一个f属于G)。

      这个公式就是Polya定理。即:N(G,C)=1/|G|*sum{|C(f)|}(对于每一个f属于G)。那么对于任意的带变换的着色计数问题,我们都可以把变换用置换群表示出来,然后对于每一个置换群考虑其|C(f)|的个数,这可以通过递推、DP、或者是矩阵快速幂来解决。所以,Polya的题最和变成了DP题- -.....
组合数学最后还讲了Polya定理基于母函数的推广,这个又更加的牛逼了一些,最后的结论非常的优美,把Polya计数问题转化成了求多项式的特定项系数问题。

      下面是一些Polya的题目:

(1)直接套公式:
         POJ 2409 Let it Bead
         UVA 10601 Cubes
         UVA 11255 Necklace
         HDU 3923 Invoker                                                 解题报告

(2)数论优化+递推 :
         POJ 2154 Color                                                     解题报告
         POJ 2888 Magic Bracelet                                      解题报告
         HUSTOJ 1569 Gift                                                 
         HDU 2865 Birthday Toy                                         解题报告
         HDU 3441 Rotation                                                解题报告

(3)难题:
         HDU 2481 Toy                                                       解题报告
         SGU 282 Isomorphism                                           解题报告
         SPOJ 422 Transposing is Even More Fun             解题报告
         HDU 3479 Code                                                  
         URAL 1661 Dodecahedron                                   

       最后附上一篇模板,自己加上最后的递推过程后就可以用来求解一般的带优化的Polya问题。

#define N 32000
int G;
long long mod;
bool notprime[N];
int prime[N],pp;
int fac[50][3],fp; //0:质数p 1:次数k 2:p^k

void init_prime() //筛质数
{
for( int i=2;i<N;i++ ){
if( !notprime[i] ) prime[ pp++ ]=i;
for( int j=0;j<pp&&i*prime[ j ]<N;j++ ){
notprime[ i*prime[ j ] ]=true;
if( i%prime[ j ]==0 ) break;
}
}
}

void fact(int a) //分解质因数
{
int n=a;
fp=0;
for(int i=0;i<pp&&prime[i]*prime[i]<=a&&n>1;i++)
if(n%prime[i]==0){
for(fac[fp][0]=prime[i],fac[fp][1]=0,fac[fp][2]=1;n%prime[i]==0;n/=prime[i],fac[fp][1]++,fac[fp][2]*=prime[i]);
fp++;
}
if(n>1) fac[fp][0]=n,fac[fp][1]=1,fac[fp++][2]=n;
}

long long getv( int n ) //计算对应的C(f)
{

}

void DFS(long long &res,int g,int phi,int d) //枚举因子
{
if(d==fp){
res=(res+1ll*phi*getv(g))%mod;
return;
}
for( int i=0,p=fac[d][2];i<=fac[d][1];i++,p/=fac[d][0] )
DFS( res,fac[d][2]/p*g,phi*(p-p/fac[d][0]),d+1 );
}

void ex_gcd( long long &x,long long &y,long long a,long long b )
{
if( !b ) x=1,y=0;
else{
ex_gcd( x,y,b,a%b );
long long t=y;
y=x-a/b*y,x=t;
}
}

long long cal()
{
fact( G );
long long ret=0,x,y;
DFS( ret,1,1,0 );
ex_gcd( x,y,G,mod );
x%=mod;
ret=(ret*x%mod+mod)%mod;
return ret;
}




  评论这张
 
阅读(5952)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017