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

GreenCloudS

 
 
 

日志

 
 

BZOJ-1875: [SDOI2009]HH去散步(动态规划+矩阵快速幂)  

2014-02-20 20:46:00|  分类: oi,bzoj,dp,矩阵 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


容易得到状态f[i][j],表示走了i步,最后一步走的边为j(记得不同方向分开处理),然后用矩阵快速幂优化就可以了。


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  •  

  • using namespace std ;

  •  

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

  • #define MAXN 210

  • #define mod 45989

  •  

  • struct mat {

  •      

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

  •      

  •     mat(  ) {

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

  •     }

  •      

  •     void I( int _n ) {

  •         n = m = _n ;

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

  •     }

  •  

  • } e , a ;

  •  

  • mat operator * ( const mat &x , const mat &y ) {

  •     mat ret ;

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

  •     rep( i , ret.n ) rep( j , ret.m ) {

  •         rep( k , x.m ) {

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

  •         }

  •     }

  •     return ret ;

  • }

  •  

  • mat power( mat x , int y ) {

  •     mat ret ;

  •     ret.I( x.n ) ;

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

  •         if ( y & 1 ) ret = ret * x ;

  •         x = x * x ;

  •     }

  •     return ret ;

  • }

  •  

  • int E[ MAXN ][ 3 ] , cnt = 0 , n , m , T , A , B ;

  •  

  • int main(  ) {

  •     scanf( "%d%d%d%d%d" , &n , &m , &T , &A , &B ) ;

  •     rep( i , m ) {

  •         int s , t ; scanf( "%d%d" , &s , &t ) ;

  •         E[ ++ cnt ][ 0 ] = s ; E[ cnt ][ 1 ] = t , E[ cnt ][ 2 ] = i ;

  •         E[ ++ cnt ][ 0 ] = t ; E[ cnt ][ 1 ] = s , E[ cnt ][ 2 ] = i ;

  •     }

  •     e.n = e.m = cnt + 1 ;

  •     rep( i , cnt ) rep( j , cnt ) if ( E[ i ][ 0 ] == E[ j ][ 1 ] && E[ i ][ 2 ] != E[ j ][ 2 ] ) {

  •         e.a[ i ][ j ] = 1 ;

  •     }

  •     a.n = cnt + 1 , a.m = 1 , a.a[ cnt + 1 ][ 1 ] = 1 ;

  •     rep( i , cnt ) if ( E[ i ][ 0 ] == A ) e.a[ i ][ cnt + 1 ] = 1 ;

  •     mat w = power( e , T ) * a ;

  •     int ans = 0 ;

  •     rep( i , cnt ) if ( E[ i ][ 1 ] == B ) ( ans += w.a[ i ][ 1 ] ) %= mod ;

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

  •     return 0 ;

  • }




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

历史上的今天

评论

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

页脚

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