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

Memento

这是一间记忆仓库~~

 
 
 

日志

 
 

HDU 2865 Birthday Toy  

2012-03-14 22:12:01|  分类: 组合数学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
       先是质因数分解,然后DFS枚举因子,对于每一个因子,我们要求它代表的置换群对应其等效后的Toy的染色方案数。这个可以推出递推关系,再用矩阵快速幂求解。 
       中间的珠子可以随便染色,那么剩下的可用颜色就为(k-1)。我们考虑的外围一圈珠子的染色方案数,设f[i]表示对n个珠子相邻之间染不同的颜色的方案数,那么第1个珠子和第n个珠子的颜色不相同,考虑第1个珠子和第n-1个珠子,假如第1个珠子和第n-1个珠子颜色不同那么总共有f[n-1]*(k-3)种方案。假如第1个珠子和第n-1个珠子颜色相同那么总共有f[n-2]*(k-2)种方案。所以f[n]=f[n-1]*(k-3)+f[n-2]*(k-2)。f[n]可以用矩阵快速幂很快的求解出来。最后再乘上k,就是这个toy的染色方案。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define N 32000
#define mod 1000000007
using namespace std;
struct matrix{
int num[2][2];
}ma[32],dp;
bool notprime[ N ];
int prime[ N ],pp;
int fac[ 50 ][ 3 ],fp;
int n,k;
long long ans;
matrix multi( matrix &a,matrix &b ){
matrix ret;
long long t;
for( int i=0;i<2;i++ )
for( int j=0;j<2;j++ ){
t=0;
for( int k=0;k<2;k++ ) t+=1ll*a.num[i][k]*b.num[k][j];
ret.num[ i ][ j ]=t%mod;
}
return ret;
}
void init_prime( void ){
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 n ){
fp=0;
memset( fac,0,sizeof( fac ) );
for( int i=0;i<pp&&n>1;i++ )
if( n%prime[ i ]==0 ){
for( fac[fp][0]=prime[i],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 ]++,fac[ fp++ ][ 2 ]=n;
}
void DFS( int g,int phi,int d ){
if( d==fp ){
g--;
dp.num[0][0]=0,dp.num[0][1]=k-1;
for( int i=0;g;g>>=1,i++ )
if( g&1 )
dp=multi( dp,ma[i] );
ans=( ans+1ll*phi*dp.num[0][0] )%mod;
return;
}
for( int i=0,p=fac[d][2];i<=fac[d][1];i++,p/=fac[d][0] )
DFS( 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;
}
}
void solve( void ){
ans=0;
fact( n );
ma[0].num[0][0]=k-3,ma[0].num[1][0]=k-2,ma[0].num[0][1]=1;
for( int i=1,temp=n/2;temp;temp>>=1,i++ ) ma[i]=multi( ma[i-1],ma[i-1] );
DFS( 1,1,0 );
ans=( ans*k )%mod;
long long x,y;
ex_gcd( x,y,n,mod );
x=( x%mod+mod )%mod;
ans=( ans*x )%mod;
cout<<ans<<endl;
}
int main( void ){
init_prime( );
while( cin>>n>>k ) solve();
}




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

历史上的今天

评论

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

页脚

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