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

Memento

这是一间记忆仓库~~

 
 
 

日志

 
 

SGU 282 Isomorphism  

2012-03-15 17:22:51|  分类: 组合数学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
        求用m种颜色对有n个点的图的边染色的不同方案数,节点之间相互置换后图相同的算同一种,n<=53,m<=1000。

        对于n个点的图,其点置换群的个数为n!个。所以需要优化。由于n<=53,我们可以考虑把n分解成一个个的最小环,把所有的使得n=x1+x2+.....+xk(x1<=x2<=....<=xk)的情况给找出来。n=53的时候满足上述的等式的解的个数也在10^6级别。那么如果对于每一种分解(x1,x2,.....xk),我们能够很快的得到满足这种形式的置换群的个数和对应的C(f)(不动染色方案数)。那么就可以在规定的时间内解决了。

       先考虑计数问题。求满足最小环的大小为(x1,x2,.....,xk)的置换群的个数。首先不考虑环的顺序,n!全排列后,对于每一个环都重复计算了xi!次,所以总个数=n!/(x1!x2!.....xk!),对于每一个环固定一个起始点后剩下的点全排列,所以要乘上(xi-1)!,最后如果两个环的大小相等,那么也重复计算了,所以还要除以ci!。最后可得计数公式=n!/(x1*x2*.....*xk*c1!*c2!*.....*cn!),其中ci为大小等于i的环的个数。这个公式计算的时候要用一点技巧,应为n<p,p为质数,所以我们可以先把分母模p后的结果算出来,求出乘法逆元x,结果=x*n!%p。

       那么对于一类点置换(x1,x2,.....,xk),我们要怎样来计算它的边置换的环的个数呢?先考虑两个点都在同一个环上的边,假设环的大小为xi,那么很容易就可以看出边置换环的个数为xi/2取下整个。再考虑两个点在不同环xi、xj上的边,可知总的边数为xi*xj,对于一条边ab,他至少要经过lcm(xi,xj)次置换后才能变回ab。那么每一个环的大小都为lcm(xi,xj)。所以边置换环的个数=xi*xj/lcm(xi,xj)=gcd(xi,xj)。这样我们就得到了边置换环个数的计算公式。
      
       这样的话我们先DFS枚举满足条件的(x1,x2,.....,xk),然后对于每一组解,求出置换群的个数a和边置换环个数b,那么相应的方案数就为a*(m+1)^b,其中m+1表示两点之间不连边也记为一种着色。最后全部相加取模后就得到了答案。

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,p;
long long nn[32],ans,tt[60];
int cyc[60][2],cp;
long long gcd( long long a,long long b ){
while( b ) b^=a^=b^=a%=b;
return a;
}
long long pow( int a ){
long long ret=1;
for( int i=0;a;a>>=1,i++ )
if( a&1 )
ret=ret*nn[i]%p;
return ret;
}
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 calcnt(){
long long x,y,t=1;
for( int i=0;i<cp;i++ ){
t=t*tt[cyc[i][1]]%p;
for( long long a=cyc[i][0],b=cyc[i][1];b;b>>=1,a=a*a%p )
if( b&1 )
t=t*a%p;
}
ex_gcd( x,y,t,p );
x=( x%p+p )%p;
return tt[n]*x%p;
}
void dfs( int d,int left ){
if( !left ){
long long t=0;
for( int i=0;i<cp;i++ ){
t+=cyc[i][0]/2*cyc[i][1]+cyc[i][1]*(cyc[i][1]-1)/2*cyc[i][0];
for( int j=i+1;j<cp;j++ )
t+=cyc[i][1]*cyc[j][1]*gcd( cyc[i][0],cyc[j][0] );
}
ans=( ans+calcnt()*pow(t) )%p;
return;
}
if( d==n ) return;
for( int i=0;i*( n-d )<=left;i++ ){
if(i) cyc[cp][0]=n-d,cyc[cp++][1]=i;
dfs( d+1,left-i*( n-d ) );
if(i) cp--;
}
}

int main(){
cin>>n>>nn[0]>>p;
for( int i=1;i<32;i++ ) nn[ i ]=nn[ i-1 ]*nn[ i-1 ]%p;
tt[0]=1;
for( int i=1;i<=n;i++ ) tt[i]=tt[ i-1 ]*i%p;
dfs( 0,n );
long long x,y;
ex_gcd( x,y,tt[n],p );
x=( x%p+p )%p;
ans=ans*x%p;
cout<<ans<<endl;
}



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

历史上的今天

评论

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

页脚

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