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

GreenCloudS

 
 
 

日志

 
 

BZOJ-2432: [Noi2011]兔农(矩阵快速幂)  

2014-07-15 21:17:00|  分类: oi,bzoj,数论,矩 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=2432


我们考虑一下所求数列mod k意义下的情况(样例):

1 1 2 3 5 0 5 5 3 0 3 3 6 2 ...

发现每个-1的地方都是0,每两个这种相邻地方的中间是一个类FIB数列,然后我们可以拆成一堆小数列的组合:

1 1 2 3 5 0 

5 5 3 0 

3 3 6 2 ...我们发现每个小数列只要开头确定了,那么这个数列就确定了,下一个数列的开头也确定了,然后小数列的开头只有k中情况,所以如果小数列数量大于k,一定会出现循环,然后对于一个小数列,就是一个斐波那契数列乘上一个常数a,设Fi a = 1 ( mod k ,那么Fi就是a的乘法逆元,如果Fi不存在,那么就这个小数列会一直持续下去,直接矩阵算掉,否则用Fi来查i,然后我就卡了,最后跑去VFK的BLOG找了个神奇的定理,模G意义下的斐波那契数列循环节不会超过6G,那么就相当好做了先预处理出一定长度的FIB数列,算出Fi最早出现的位置,然后每次查一下就好了,然后一个数列一个数列的跳,如果循环了就把循环用矩阵跳掉,这样似乎就可以O(k log k)了QAQ。


代码(注意处理小数列的循环的时候,我们维护模p意义下的数要用矩阵快速幂去算,因为这个卡了好久额QAQ):

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  •   

  • using namespace std ;

  •   

  • #define REP( i , l , r ) for ( int i = l ; i <= r ; ++ i )

  • #define rep( i , x ) for ( int i = 0 ; i ++ < x ; )

  • #define DOWN( i , r , l ) for ( int i = r ; i >= l ; -- i )

  • #define Rep( i , x ) for ( int i = 0 ; i < x ; ++ i )

  •   

  • const int maxk = 1010000 ;

  •   

  • typedef long long ll ;

  •   

  • struct mat {

  •         int n , m , a[ 4 ][ 4 ] ;

  •         mat(  ) {

  •                 n = m = 0 ;

  •                 memset( a , 0 , sizeof( a ) ) ;

  •         }

  •         inline void Init( int _n ) {

  •                 n = m = _n ;

  •                 memset( a , 0 , sizeof( a ) ) ;

  •                 rep( i , n ) a[ i ][ i ] = 1 ;

  •         }

  • } e ;

  •   

  • inline mat mul( const mat &x , const mat &y , int mod ) {

  •         mat ret ;

  •         ret.n = x.n , ret.m = y.m ;

  •         rep( i , x.n ) rep( j , y.m ) rep( k , x.m ) {

  •                 ret.a[ i ][ j ] = ( ret.a[ i ][ j ] + ( ll ) x.a[ i ][ k ] * y.a[ k ][ j ] % mod ) % mod ;

  •         }

  •         return ret ;

  • }

  •   

  • inline mat power( mat x , ll cnt , int mod ) {

  •         mat ret ; ret.Init( x.n ) ;

  •         for ( ; cnt ; cnt >>= 1 ) {

  •                 if ( cnt & 1 ) ret = mul( ret , x , mod ) ;

  •                 x = mul( x , x , mod ) ;

  •         }

  •         return ret ;

  • }

  •   

  • inline void Init_mat(  ) {

  •         e.n = e.m = 2 , e.a[ 1 ][ 1 ] = 0 , e.a[ 1 ][ 2 ] = e.a[ 2 ][ 1 ] = e.a[ 2 ][ 2 ] = 1 ;

  • }

  •   

  • inline void getf( int f1 , int f2 , ll cnt , int mod , int &x , int &y ) {

  •         if ( cnt == 1 ) {

  •                 y = f1 ; return ;

  •         }

  •         if ( cnt == 2 ) {

  •                 x = f1 , y = f2 ; return ;      

  •         }

  •         mat rec = power( e , cnt - ll( 2 ) , mod ) , ret ;

  •         ret.n = 2 , ret.m = 1 , ret.a[ 1 ][ 1 ] = f1 % mod , ret.a[ 2 ][ 1 ] = f2 % mod ;

  •         ret = mul( rec , ret , mod ) ;

  •         x = ret.a[ 1 ][ 1 ] , y = ret.a[ 2 ][ 1 ] ;

  • }

  •   

  • inline int gcd( int x , int y ) {

  •         if ( x < y ) swap( x , y ) ;

  •         for ( int z ; y ; z = y , y = x % y , x = z ) ;

  •         return x ;

  • }

  •   

  • void exgcd( int a , int b , int &x , int &y ) {

  •         if ( ! b ) {

  •                 x = 1 , y = 0 ; return ;

  •         }

  •         int tx , ty ; exgcd( b , a % b , tx , ty ) ;

  •         x = ty , y = tx - ( a / b ) * ty ;

  • }

  •   

  • inline int Inv( int a , int mod ) {

  •         if ( gcd( a , mod ) != 1 ) return 0 ;

  •         int x , y ;

  •         if ( a > mod ) exgcd( a , mod , x , y ) ; else exgcd( mod , a , y , x ) ;

  •         if ( x > 0 ) x %= mod ;

  •         if ( x < 0 ) x += mod * ( ( - x ) / mod + ( ( - x ) % mod > 0 ) ) ;

  •         return x ;

  • }

  •   

  • int pos[ maxk ] , k , p , f1 , f2 ;

  • ll n ;

  •   

  • int last[ maxk ] , cnt = 0 ;

  • ll sum[ maxk ] ;

  •   

  • int main(  ) {

  •         Init_mat(  ) ;

  •         memset( pos , 0 , sizeof( pos ) ) ;

  •         scanf( "%lld%d%d" , &n , &k , &p ) ;

  •         f1 = f2 = 1 ;

  •         for ( int t , i = 3 , j = 6 * k ; i <= j ; ++ i ) {

  •                 t = ( f1 + f2 ) % k ;

  •                 f1 = f2 ; f2 = t ;

  •                 if ( ! pos[ t ] ) pos[ t ] = i ;

  •         }

  •         memset( last , 0 , sizeof( last ) ) ;

  •         sum[ cnt = 0 ] = 0 ;

  •         if ( n <= 2 ) {

  •                 printf( "1\n" ) ; return 0 ;

  •         }

  •         for ( int a = 1 , b1 = 1 , b2 = 1 , len , inv , x , y ; ; ) {

  •                 inv = Inv( a , k ) ;

  •                 if ( ! inv || ! pos[ inv ] || n <= pos[ inv ] ) {

  •                         getf( b1 , b2 , n , p , x , y ) ;

  •                         if ( y % k == 1 ) y = ( y - 1 + p ) % p ;

  •                         printf( "%d\n" , y ) ;

  •                         return 0 ;

  •                 }

  •                 len = pos[ inv ] ;

  •                 ++ cnt ;

  •                 sum[ cnt ] = sum[ cnt - 1 ] + ll( len ) , last[ a ] = cnt ;

  •                 getf( a , a , len - 1 , k , x , y ) ; a = y ;

  •                 getf( b1 , b2 , len , p , x , y ) ; y = ( y - 1 + p ) % p ;

  •                 b1 = ( x + y ) % p ; b2 = ( y + b1 ) % p ;

  •                 n -= len ;

  •                 if ( last[ a ] && n > sum[ cnt ] - sum[ last[ a ] - 1 ] ) {

  •                         mat Ex , Ea , Eb , Et ;

  •                         Ea.n = Ea.m = Eb.n = Eb.m = 3 ;

  •                         Ea.a[ 1 ][ 1 ] = 0 , Ea.a[ 1 ][ 2 ] = 1 , Ea.a[ 1 ][ 3 ] = 0 ;

  •                         Ea.a[ 2 ][ 1 ] = 1 , Ea.a[ 2 ][ 2 ] = 1 , Ea.a[ 2 ][ 3 ] = 0 ;

  •                         Ea.a[ 3 ][ 1 ] = 0 , Ea.a[ 3 ][ 2 ] = 0 , Ea.a[ 3 ][ 3 ] = 1 ;

  •                         Eb.a[ 1 ][ 1 ] = 1 , Eb.a[ 1 ][ 2 ] = 1 , Eb.a[ 1 ][ 3 ] = p - 1 ;

  •                         Eb.a[ 2 ][ 1 ] = 1 , Eb.a[ 2 ][ 2 ] = 2 , Eb.a[ 2 ][ 3 ] = p - 2 ;

  •                         Eb.a[ 3 ][ 1 ] = 0 , Eb.a[ 3 ][ 2 ] = 0 , Eb.a[ 3 ][ 3 ] = 1 ;

  •                         Ex.Init( 3 ) ;

  •                         REP( i , last[ a ] , cnt ) {

  •                                 Ex = mul( power( Ea , sum[ i ] - sum[ i - 1 ] - 2 , p ) , Ex , p ) ;

  •                                 Ex = mul( Eb , Ex , p ) ;

  •                         }

  •                         ll sz = sum[ cnt ] - sum[ last[ a ] - 1 ] , t ;

  •                         if ( n % sz ) {

  •                                 t = n / sz ;

  •                                 n %= sz ;

  •                         } else {

  •                                 t = n / sz - 1 ;

  •                                 n = sz ;

  •                         }

  •                         Et.n = 3 , Et.m = 1 , Et.a[ 1 ][ 1 ] = b1 , Et.a[ 2 ][ 1 ] = b2 , Et.a[ 3 ][ 1 ] = 1 ;

  •                         Et = mul( power( Ex , t , p ) , Et , p ) ;

  •                         b1 = Et.a[ 1 ][ 1 ] , b2 = Et.a[ 2 ][ 1 ] ;

  •                 }

  •         }

  •         return 0 ;

  • }



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

历史上的今天

评论

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

页脚

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