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

Memento

这是一间记忆仓库~~

 
 
 

日志

 
 

HDU 2481 Toy  

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

  下载LOFTER 我的照片书  |
       08年成都现场赛的神题,传说现场就清华一支队伍出了此题。这题的难点在于递推方程。网上有万物皆数大神和AekdyCoin大神的详细解题报告,先找递推式,然后用矩阵快速幂求答案的方法,这种方法速度很快,但是递推过程比较繁琐,并且代码量不小。另一种方法是直接转化为生成树计数问题,然后根据题目的特殊性质对行列式进行化简,代码比较短。还有一个很恶心的地方就是这题的取模数<=10^18,所以long long装不下,要二分模拟乘法,贴了一个别人的模板- -

       我实现了一下第一种方法,最后惊奇的发现居然登顶了,看来质因数分解后DFS在大数据的时候效率还是很不错的- -

       HDU 2481 Toy - endlesscount - Memento
 

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



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

历史上的今天

评论

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

页脚

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