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

那一日,泪水打湿雪花冰冷的心

曾经的滋味,回忆在一次次的离合中,回眸时,那一刻,如涟漪般在一刹那融化

 
 
 

日志

 
 

POJ 2888  

2010-07-16 22:30:40|  分类: poj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
有限制的应用polya来计数的问题,注意到burnside引理说使得各个运算不变的个数总和除以运算的总个数,polya是寻找循环节,使得每个循环节涂色一样,再注意到,这个题中,循环节中的数都是依次排列,所以对于循环节为k的,只要用矩阵的幂,求得带限制的个数,就可以像2154那题一样,枚举因数,求得欧拉函数来求解,最后除法的时候,只要用扩展欧几里得求逆即可,题意说明互质,因而逆存在
#include<cstdio>
#include<cstring>
int a[50],b[50],q[20][20],q4[50][20][20];
int n,p=9973,m,ret,t,n0,d,k,a1,a2,w;
int euler(int n){
    int m=1;
    for(int i=2;i*i<=n;i++)
      if(!(n%i)){
        n/=i;
        m*=(i-1);
        while(!(n%i)){
          m*=i;
          n/=i;
        }     
      }
    if(n!=1)
      m*=(n-1);
    return m%p;
}
void init(){
memset(q4,0,sizeof(q4));
memcpy(q4[1],q,sizeof(q));
for(int i=2;(1<<(i-1))<=n0;++i)
for(int j0=0;j0<m;++j0)
for(int j1=0;j1<m;++j1)
for(int j2=0;j2<m;++j2)
q4[i][j0][j1]=(q4[i][j0][j1]+q4[i-1][j0][j2]*q4[i-1][j2][j1])%p;
}
int aa(int y){
int q2[20][20],q3[20][20];
memset(q2,0,sizeof(q2));
for(int i=0;i<m;++i)
q2[i][i]=1;
int x=1;
while(y){
if(y&1){
memset(q3,0,sizeof(q3));
for(int i=0;i<m;++i)
for(int j=0;j<m;++j)
for(int t=0;t<m;++t)
q3[i][j]=(q3[i][j]+q2[i][t]*q4[x][t][j])%p;
memcpy(q2,q3,sizeof(q3));
}
++x;
y>>=1;
}
int ret=0;
for(int i=0;i<m;++i)
ret+=q2[i][i];
return ret%p;
}
void solve(int x,int y){
if(x==k){
ret=(ret+aa(y)*euler(n0/y))%p;
return ;
}
if(!((1<<x)&d)){
solve(x+1,y);
return ;
}
for(int i=1;i<=b[x];++i){
y*=a[x];
solve(x+1,y);
}
}
void gcd(int a,int b,int &x,int &y){
if(b==0){
x=1;
y=0;
return ;
}
gcd(b,a%b,y,x);
y-=(a/b)*x;
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&n,&m,&k);
if(m==1){
if(!k)
printf("%d\n",1%p);
else {
for(int i=0;i<k;++i)
scanf("%d%d",&a1,&a2);
printf("0\n");
}
continue;
}
for(int i=0;i<m;++i)
for(int j=0;j<m;++j)
q[i][j]=1;
for(int i=0;i<k;++i){
scanf("%d%d",&a1,&a2);
q[a1-1][a2-1]=q[a2-1][a1-1]=0;
}
ret=0;n0=n;k=0;
init();
for(int i=2;n>1;i=i*i<=n?i+1:n)
if(n%i==0){
a[k]=i;
b[k]=0;
while(n%i==0){
n/=i;
++b[k];
}
++k;
}
for(d=0;d<(1<<k);++d)
solve(0,1);
int x,y;
gcd(n0%p,p,x,y);
printf("%d\n",(ret*((x%p+p)%p))%p);
}
return 0;
}
  评论这张
 
阅读(682)| 评论(2)
推荐 转载

历史上的今天

评论

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

页脚

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