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

GreenCloudS

 
 
 

日志

 
 

BZOJ-1494: [NOI2007]生成树计数(状压DP+矩阵快速幂)  

2014-05-31 09:33:00|  分类: oi,bzoj,dp,最小 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


题目坑爹的把人往基尔霍夫矩阵上带。。。我们发现连边只有相邻不大于k的节点之间才有,那么状压一下,用最小表示法维护一下最后k个节点的状态,然后我们发现方程是线性的,于是可以用矩阵快速幂加速之,总复杂度O( S^3 log n ) S表示最小表示法下的状态数,k=5时S=52。


代码:

  • #include <cstdio>

  • #include <cstring>

  • #include <cstdlib>

  •  

  • #define DOWN( i , y , x ) for ( int i = y ; i >= x ; -- i )

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

  • #define REP( i , x , y ) for ( int i = x ; i <= y ; ++ i )

  •  

  • typedef long long ll ;

  •  

  • const int maxn = 55 , maxk = 8 ;

  • const ll mod = 65521 ;

  •  

  • inline void swap( int &x , int &y ) {

  •     int z = x ; x = y ; y = z ;

  • }

  •  

  • struct mat {

  •      

  •     ll a[ maxn ][ maxn ] ;

  •     int n , m ;

  •      

  •     mat(  ) {

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

  •     }

  •      

  •     void INIT( int _n ) {

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

  •         n = m = _n ;

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

  •     }

  •      

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

  •         mat temp ; temp.n = n , temp.m = x.m ;

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

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

  •         }

  •         return temp ;

  •     }

  •      

  • } in , ans , tra ;

  •  

  • inline mat power( mat val , ll cnt ) {

  •     mat temp ; temp.INIT( val.n ) ;

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

  •         if ( cnt & 1 ) temp = temp * val ;

  •         val = val * val ;

  •     }

  •     return temp ;

  • }

  •  

  • int num[ 10000 ] , k , cnt = 0 , Sta[ maxn ] ;

  • ll n ;

  •  

  • void Print( int sta ) {

  •     int rec[ maxk ] , ret = 0  ;

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

  •     for ( ; sta ; sta /= 5 ) rec[ ++ ret ] = sta % 5 ;

  •     DOWN( i , k , 1 ) printf( "%d" , rec[ i ] ) ;

  •     printf( "\n" ) ;

  • }

  •  

  • void getnum( int now , int pos , int sta ) {

  •     if ( now == k + 1 ) {

  •         Sta[ num[ sta ] = ++ cnt ] = sta ;

  •         return ;

  •     }

  •     REP( i , 0 , ( pos - 1 ) ) getnum( now + 1 , pos , sta * 5 + i ) ;

  •     getnum( now + 1 , pos + 1 , sta * 5 + pos ) ;

  • }

  •  

  • struct Uset {

  •      

  •     int father[ maxk ] ;

  •      

  •     Uset(  ) {

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

  •     }

  •      

  •     inline int getfa( int now ) {

  •         int i ; for ( i = now ; father[ i ] ; i = father[ i ] ) ;

  •         for ( int j = now , k ; father[ j ] ; k = father[ j ] , father[ j ] = i , j = k ) ;

  •         return i ;

  •     }

  •      

  •     inline void merge( int x , int y ) {

  •         int v = getfa( x ) , u = getfa( y ) ;

  •         if ( v > u ) swap( v , u ) ;

  •         if ( v != u ) father[ u ] = v ;

  •     }

  •      

  • } ;

  •  

  • inline int trans( Uset &S ) {

  •     int sta = 0 , rec[ maxk ] , ret = 0 ;

  •     rep( i , k ) {

  •         if ( i == S.getfa( i ) ) rec[ i ] = ret ++ ;

  •         sta = sta * 5 + rec[ S.getfa( i ) ] ;

  •     }

  •     return sta ;

  • }

  •  

  • void getin( int now , int pos , Uset &S ) {

  •     if ( now == k + 1 ) {

  •         in.a[ num[ trans( S ) ] ][ 1 ] ++ ; 

  •         return ;

  •     }

  •     if ( pos == now ) {

  •         getin( now + 1 , 1 , S ) ;

  •         return ;

  •     }

  •     Uset temp ;

  •     if ( S.getfa( now ) != S.getfa( pos ) ) {

  •         temp = S ;

  •         S.merge( now , pos ) ;

  •         getin( now , pos + 1 , S ) ;

  •         S = temp ;

  •     }

  •     getin( now , pos + 1 , S ) ;

  • }

  •  

  • int mul[ maxk ] ;

  •  

  • Uset itrans( int sta ) {

  •     Uset S ;

  •     int rec[ maxk ] , ret ;

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

  •     rep( i , k ) {

  •         ret = ( sta / mul[ k - i ] ) % 5 ;

  •         if ( ! rec[ ret ] ) rec[ ret ] = i ; else {

  •             S.merge( i , rec[ ret ] ) ;

  •         }

  •     }

  •     return S ;

  • }

  •  

  • void gettra( int now , int pos , Uset &S ) {

  •     if ( now == k + 1 ) {

  •         bool flag = false ;

  •         REP( i , 2 , ( k + 1 ) ) if ( S.getfa( i ) == S.getfa( 1 ) ) {

  •             flag = true ; break ;

  •         }

  •         if ( flag ) {

  •             int rec[ maxk ] , ret = 0 , sta = 0 , temp ; 

  •             rep( i , k + 1 ) rec[ i ] = - 1 ;

  •             rep( i , k ) {

  •                 temp = S.getfa( i + 1 ) ;

  •                 if ( rec[ temp ] == - 1 ) rec[ temp ] = ret ++ ;

  •                 sta = sta * 5 + rec[ temp ] ;

  •             }

  •             tra.a[ num[ sta ] ][ pos ] ++ ;

  •         }

  •         return ;

  •     }

  •     if ( S.getfa( k + 1 ) != S.getfa( now ) ) {

  •         Uset temp = S ;

  •         S.merge( k + 1 , now ) ;

  •         gettra( now + 1 , pos , S ) ;

  •         S = temp ;

  •     }

  •     gettra( now + 1 , pos , S ) ;

  • }

  •  

  • int main(  ) {

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

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

  •     if ( n <= k ) {

  •         ll ret = 1 ;

  •         rep( i , ( n - 2 ) ) ( ret *= ll( n ) ) %= mod ;

  •         printf( "%lld\n" , ret ) ;

  •         return 0 ;

  •     }

  •     getnum( 1 , 0 , 0 ) ;

  •     in.n = cnt , in.m = 1 ;

  •     Uset S ;

  •     getin( 1 , 1 , S ) ;

  •     mul[ 0 ] = 1 ; rep( i , k ) mul[ i ] = mul[ i - 1 ] * 5 ;

  •     tra.n = tra.m = cnt ;

  •     rep( i , cnt ) {

  •         S = itrans( Sta[ i ] ) ;

  •         gettra( 1 , i , S ) ;

  •     }

  •     ans = power( tra , n - ll( k ) ) * in ;

  •     printf( "%lld\n" , ans.a[ 1 ][ 1 ] ) ;

  •     return 0 ;

  • }



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

历史上的今天

评论

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

页脚

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