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

Memento

这是一间记忆仓库~~

 
 
 

日志

 
 

HDU 3923 Invoker  

2012-03-14 21:04:43|  分类: 组合数学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
       第一次碰见的Polya题目就是这题,是多校的题目,当时我们队巨菜,我连啥是Polya都不知道- -,一看完题感觉应该蛮水,就是个组合计数什么的,想都没想就丢给了yinthewind,结果悲剧了一下午...... 
       简单的Polya计数问题,对于旋转的置换群直接计算sum{n^gcd(i,n)},1<=i<=n。对于翻转的情况,分奇偶讨论:n为偶数时,置换群有两种,一种是对称轴经过两个端点的置换群,其环的个数为n/2+1,总共有n/2个这样的置换群;另一种是不经过端点的,环个数为n/2,有n/2个。当n为奇数时,置换群就一种,环个数为(n+1)/2,总共有n个。

#include<cstdio>
#include<cstring>
#include<iostream>
#define mod 1000000007
using namespace std;
int nn[ 32 ];
int gcd( int a,int b ){
while( b ) b^=a^=b^=a%=b;
return a;
}
long long ex_gcd( long long &x,long long &y,long long a,long long b ){
if(!b){
x=1,y=0;
return a;
}
long long g=ex_gcd( x,y,b,a%b );
int tmp=y;
y=x-a/b*y,x=tmp;
return g;
}
long long pow( int a ){
long long ret=1;
for( int i=0;a;a>>=1,i++ )
if( a&1 )
ret=( ret*nn[i] )%mod;
return ret;
}
int main( void ){
int T,n,k;
long long x,y;
cin>>T;
for( int cas=1;cas<=T;cas++ ){
cin>>k>>n;
nn[ 0 ]=k;
for( int i=1;i<32;i++ )
nn[ i ]=(1ll*nn[ i-1 ]*nn[ i-1 ])%mod;
long long ans=0;
for( int i=1;i<=n;i++ ) ans=ans+pow(gcd( i,n ));
ans%=mod;
if( n%2 ){
ans=(ans+(n*pow((n+1)/2))%mod)%mod;
}
else{
ans=(ans+(n/2*pow(n/2)%mod ))%mod;
ans=(ans+(n/2*pow(n/2+1)%mod))%mod;
}
ex_gcd( x,y,2*n,mod );
x=(x+mod)%mod;
ans=(ans*x)%mod;
cout<<"Case #"<<cas<<": "<<ans<<endl;
}
}





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

历史上的今天

评论

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

页脚

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