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

Memento

这是一间记忆仓库~~

 
 
 

日志

 
 

POJ 2888 Magic Bracelet  

2012-03-14 20:45:32|  分类: 组合数学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
       在一般的项链染色计数问题的基础上加了一些限制条件。给定m种珠子,和k个限制条件,表示某两种珠子不能串在一起,问有多少种合法的方案。n<=10^9,m<=10。
       因为相邻的珠子旋转后还是相邻,对于处在同一个环上的珠子,我们其实可以把它等价的看成一颗珠子,所以这题也可以用数论优化。剩下的问题就是怎么求解n个不动的珠子的合法方案数了,这个很明显可以DP,但是还要解决的一个问题就是n太大的话DP也不能解决,这个时候如果对数据敏感的话,就会发现m<=10,我们可以用一个m*m的矩阵来描述不同种类的珠子之间的关系,初始化为1,如果i,j不能相邻,那么ma[i][j]=0。这个矩阵自乘n次后得到的矩阵系数之和就是我们要的东西。一个快速幂就搞定了。

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




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

历史上的今天

评论

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

页脚

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