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

GreenCloudS

 
 
 

日志

 
 

BZOJ-1009: [HNOI2008]GT考试(KMP+DP+矩阵快速幂)  

2014-02-03 13:52:00|  分类: oi,BZOJ,DP,KMP, |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


我们设f(i,j)为原串中匹配到第i为,不吉利号码匹配到第j位的数目,那么我们可以用矩阵来表示状态转移方程为:

BZOJ-1009: [HNOI2008]GT考试(KMP+DP+矩阵快速幂) - cjjlsdy - cjjlsdy的博客

a矩阵用KMP算法来预处理,然后用矩阵快速幂即可。


代码:

  • #include <cstdio>
  • #include <algorithm>
  • #include <cstring>
  •  
  • using namespace std ;
  •  
  • #define rep( i , x ) for ( int i = 0 ; i < x ; ++ i )
  • #define MAXN 25
  •  
  • struct mat {
  •             
  •             int a[ MAXN ][ MAXN ] , n , m ;
  •             
  •             mat(  ) {
  •                         n = m = 0 ;
  •                         memset( a , 0 , sizeof( a ) ) ;
  •             }
  •             
  •             void I( int _n ) {
  •                         n = m = _n ;
  •                         rep( i , n ) a[ i ][ i ] = 1 ;
  •             }
  •             
  • } ori , ans ;
  •  
  • int mod ;
  •  
  • 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 cnt ) {
  •             mat ret ; ret.I( x.n ) ;
  •             for ( ; cnt ; cnt >>= 1 ) {
  •                         if ( cnt & 1 ) ret = ret * x ;
  •                         x = x * x ;
  •             }
  •             return ret ;
  • }
  •  
  • int n , m , s[ MAXN ] ;
  • int pre[ MAXN ] ;
  •  
  • void kmp(  ) {
  •             memset( pre , 0 , sizeof( pre ) ) ;
  •             for ( int i = 1 , j = 0 ; i ++ < m ; ) {
  •                         for ( ; j && s[ i ] != s[ j + 1 ] ; j = pre[ j ] ) ;
  •                         if ( s[ j + 1 ] == s[ i ] ) ++ j ;
  •                         pre[ i ] = j ;
  •             }
  • }
  •  
  • int main(  ) {
  •             scanf( "%d%d%d" , &n , &m , &mod ) ;
  •             for ( int i = 0 ; i ++ < m ; ) {
  •                         int ch ; for ( ch = getchar(  ) ; ! ( ch >= '0' && ch <= '9' ) ; ch = getchar(  ) ) ;
  •                         s[ i ] = ch - '0' ;
  •             }
  •             kmp(  ) ;
  •             ori.n = ori.m = m ;
  •             rep( i , m ) {
  •                         rep( j , 10 ) {
  •                                      int k ;
  •                                     for ( k = i ; k && s[ k + 1 ] != j ; k = pre[ k ] ) ;
  •                                      if ( s[ k + 1 ] == j ) ++ k ;
  •                                      if ( k < m ) ++ ori.a[ k ][ i ] ;
  •                         }
  •             }
  •             ans.n = m , ans.m = 1 ;
  •             ans.a[ 0 ][ 0 ] = 1 ;
  •             ans = power( ori , n ) * ans ;
  •             int Ans = 0 ;
  •             rep( i , m ) ( Ans += ans.a[ i ][ 0 ] ) %= mod ;
  •             printf( "%d\n" , Ans ) ;
  •             return 0 ;
  • }



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

历史上的今天

评论

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

页脚

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