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

GreenCloudS

 
 
 

日志

 
 

BZOJ-3530: [Sdoi2014]数数(AC自动机+DP)  

2014-04-21 22:10:00|  分类: oi,bzoj,AC自动机 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


AC自动机上跑一下DP,前导0就讨论一下。


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <queue>

  • #include <vector>

  •   

  • using namespace std ;

  •   

  • #define fail( t ) Node[ t ].fail

  • #define child( t , x ) Node[ t ].child[ x ]

  • #define flag( t ) Node[ t ].flag

  •   

  • const int mod = 1000000007 ;

  • const int maxn = 1510 ;

  •   

  • struct node {

  •     int fail , child[ 10 ] ;

  •     bool flag ;

  •     node(  ) {

  •         fail = 0 , flag = false ;

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

  •     }

  • } Node[ maxn ] ;

  •   

  • char N[ maxn ] , s[ maxn ] ;

  • int m , V = 0 , lenN ;

  •   

  • queue < int > q ;

  •   

  • void build_fail(  ) {

  •     while ( ! q.empty(  ) ) q.pop(  ) ;

  •     for ( int i = 0 ; i < 10 ; ++ i ) if ( child( 0 , i ) ) {

  •         q.push( child( 0 , i ) ) ;

  •     }

  •     while ( ! q.empty(  ) ) {

  •         int v = q.front(  ) ; q.pop(  ) ;

  •         for ( int i = 0 ; i < 10 ; ++ i ) if ( child( v , i ) ) {

  •             int t = fail( v ) ;

  •             for ( ; t && ! child( t , i ) ; t = fail( t ) ) ;

  •             fail( child( v , i ) ) = child( t , i ) ;

  •             q.push( child( v , i ) ) ;

  •         }

  •     }

  • }

  •   

  • vector < int > E[ maxn ] ;

  •   

  • void dfs( int v , bool state ) {

  •     flag( v ) |= state ;

  •     for ( vector < int > :: iterator p = E[ v ].begin(  ) ; p != E[ v ].end(  ) ; ++ p ) {

  •         dfs( *p , flag( v ) ) ;

  •     }

  • }

  •   

  • int trans[ maxn ][ 10 ] , dp[ maxn ][ maxn ] , ans = 0 ;

  •   

  • void update( int &x , int val ) {

  •     ( x += val ) %= mod ;

  • }

  •   

  • int fun[ maxn ][ maxn ][ 2 ] ;

  •   

  • void cal(  ) {

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

  •     for ( int i = 0 ; i < lenN ; ++ i ) {

  •         for ( int j = 1 ; j < 10 ; ++ j ) if ( ! flag( trans[ 0 ][ j ] ) ) {

  •             update( dp[ i + 1 ][ trans[ 0 ][ j ] ] , 1 ) ;

  •         }

  •         if ( i == lenN - 1 ) break ;

  •         for ( int j = 0 ; j <= V ; ++ j ) if ( dp[ i ][ j ] ) {

  •             for ( int k = 0 ; k < 10 ; ++ k ) if ( ! flag( trans[ j ][ k ] ) ) {

  •                 update( dp[ i + 1 ][ trans[ j ][ k ] ] , dp[ i ][ j ] ) ;

  •             }

  •         }

  •     }

  •     for ( int i = 0 ; i <= V ; ++ i ) update( ans , dp[ lenN - 1 ][ i ] ) ;

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

  •     int z = N[ 1 ] - '0' ;

  •     for ( int i = 1 ; i < z ; ++ i ) if ( ! flag( trans[ 0 ][ i ] ) ) {

  •         fun[ 1 ][ trans[ 0 ][ i ] ][ 0 ] ++ ;

  •     }

  •     if ( ! flag( trans[ 0 ][ z ] ) ) fun[ 1 ][ trans[ 0 ][ z ] ][ 1 ] ++ ;

  •     for ( int i = 1 ; i < lenN ; ++ i ) {

  •         for ( int j = 0 ; j <= V ; ++ j ) {

  •             if ( fun[ i ][ j ][ 0 ] ) {

  •                 for ( int k = 0 ; k < 10 ; ++ k ) if ( ! flag( trans[ j ][ k ] ) ) {

  •                     update( fun[ i + 1 ][ trans[ j ][ k ] ][ 0 ] , fun[ i ][ j ][ 0 ] ) ;

  •                 }

  •             }

  •             if ( fun[ i ][ j ][ 1 ] ) {

  •                 z = N[ i + 1 ] - '0' ;

  •                 for ( int k = 0 ; k < z ; ++ k ) if ( ! flag( trans[ j ][ k ] ) ) {

  •                     update( fun[ i + 1 ][ trans[ j ][ k ] ][ 0 ] , fun[ i ][ j ][ 1 ] ) ;

  •                 }

  •                 if ( ! flag( trans[ j ][ z ] ) ) {

  •                     update( fun[ i + 1 ][ trans[ j ][ z ] ][ 1 ] , fun[ i ][ j ][ 1 ] ) ;

  •                 }

  •             }

  •         }

  •     }

  •     for ( int i = 0 ; i <= V ; ++ i ) {

  •         update( ans , fun[ lenN ][ i ][ 0 ] ) ;

  •         update( ans , fun[ lenN ][ i ][ 1 ] ) ;

  •     }

  • }

  •   

  • int main(  ) {

  •     scanf( "%s%d" , N + 1 , &m ) ;

  •     lenN = strlen( N + 1 ) ;

  •     while ( m -- ) {

  •         scanf( "%s" , s ) ;

  •         int t = 0 ;

  •         for ( int i = 0 , len = strlen( s ) ; i < len ; ++ i ) {

  •             int ch = s[ i ] - '0' ;

  •             if ( ! child( t , ch ) ) child( t , ch ) = ++ V ;

  •             t = child( t , ch ) ;

  •         }

  •         flag( t ) = true ;

  •     }

  •     build_fail(  ) ;

  •     for ( int i = 0 ; i ++ < V ; ) E[ fail( i ) ].push_back( i ) ;

  •     dfs( 0 , false ) ;

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

  •     for ( int i = 0 ; i <= V ; ++ i ) {

  •         for ( int j = 0 ; j < 10 ; ++ j ) {

  •             int t = i ;

  •             for ( ; t && ! child( t , j ) ; t = fail( t ) ) ;

  •             trans[ i ][ j ] = child( t , j ) ;

  •         }

  •     }

  •     cal(  ) ;

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

  •     return 0 ;

  • }



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

历史上的今天

评论

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

页脚

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