BZOJ-1875: [SDOI2009]HH去散步（动态规划+

题目：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 ;

}