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

GreenCloudS

 
 
 

日志

 
 

BZOJ-1898: [Zjoi2004]Swamp 沼泽鳄鱼(矩阵快速幂)  

2014-02-02 21:05:00|  分类: 快速幂,矩阵乘法, |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


矩阵快速幂随便搞一搞就行了。


代码:

  • #include <cstdio>
  • #include <algorithm>
  • #include <cstring>
  •  
  • using namespace std ;
  •  
  • #define mod 10000
  • #define MAXN 55
  •  
  • struct mat {
  •      
  •     int n , m , a[ MAXN ][ MAXN ] ;
  •      
  •     mat(  ) {
  •         memset( a , 0 , sizeof( a ) ) ;
  •         n = m = 0 ;
  •     }
  •      
  •     void Init_I( int _n ) {
  •         n = m = _n ;
  •         for ( int i = 0 ; i < n ; ++ i ) a[ i ][ i ] = 1 ;
  •     }
  •      
  • } Map[ 12 ] , temp , ans ;
  •  
  • mat operator * ( const mat &x , const mat &y ) {
  •     mat ret ; 
  •     ret.n = x.n , ret.m = y.m ;
  •     for ( int i = 0 ; i < ret.n ; ++ i ) {
  •         for ( int j = 0 ; j < ret.m ; ++ j ) {
  •             for ( int k = 0 ; k < x.m ; ++ k ) {
  •                 ( ret.a[ i ][ j ] += x.a[ i ][ k ] * y.a[ k ][ j ] ) %= mod ;
  •             }
  •         }
  •     }
  •     return ret ;
  • }
  •  
  • mat Pow( const mat &x , int cnt ) {
  •     mat rec , ret = x ;
  •     rec.Init_I( x.n ) ;
  •     for ( ; cnt ; cnt >>= 1 ) {
  •         if ( cnt & 1 ) rec = rec * ret ;
  •         ret = ret * ret ;
  •     }
  •     return rec ;
  • }
  •  
  • int n , m , S , T , k , nf , w[ 4 ] ;
  •  
  • int main(  ) {
  •     scanf( "%d%d%d%d%d" , &n , &m , &S , &T , &k ) ;
  •     Map[ 0 ].n = Map[ 0 ].m = n ;
  •     while ( m -- ) {
  •         int s , t ; scanf( "%d%d" , &s , &t ) ;
  •         Map[ 0 ].a[ s ][ t ] = Map[ 0 ].a[ t ][ s ] = 1 ;
  •     }
  •     for ( int i = 1 ; i < 12 ; ++ i ) Map[ i ] = Map[ i - 1 ] ;
  •     scanf( "%d" , &nf ) ;
  •     while ( nf -- ) {
  •         int t ; scanf( "%d" , &t ) ;
  •         for ( int i = 0 ; i < t ; ++ i ) scanf( "%d" , &w[ i ] ) ;
  •         for ( int i = 0 ; i < 12 ; ++ i ) {
  •             int x = w[ i % t ] ;
  •             if ( i ) {
  •                 for ( int j = 0 ; j < n ; ++ j ) Map[ i - 1 ].a[ j ][ x ] = 0 ;
  •             }
  •             for ( int j = 0 ; j < n ; ++ j ) Map[ i ].a[ x ][ j ] = 0 ;
  •         }
  •     }
  •     temp.Init_I( n ) ;
  •     ans.Init_I( n ) ;
  •     for ( int i = 0 ; i < 12 ; ++ i ) temp = temp * Map[ i ] ;
  •     ans = ans * Pow( temp , k / 12 ) ;
  •     for ( int i = 0 ; i < k % 12 ; ++ i ) ans = ans * Map[ i ] ;
  •     printf( "%d\n" , ans.a[ S ][ T ] ) ;
  •     return 0 ; 
  • }



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

历史上的今天

评论

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

页脚

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