[SCOI2009]迷路

看到题,如果边权都是1就很好做了(矩阵快速幂一波带走)

但是呢。。。

这题边权有10 啊??

zjk 太巨了。。

拆点。。 比如一个点到另一个是8,那么就拆成八个边权为1,前七个只和后一个相连,最后一个和下一个相连。思路和分层图很像。 不多说了。。

/**************************************************************
    Problem: 1297
    User: yi_han
    Language: C++
    Result: Accepted
    Time:2100 ms
    Memory:1416 kb
****************************************************************/

/*Heroes Never Die!*/
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
using namespace std;
#define MAXN 101
#define P 2009

int n , t , k;

struct matrx { int a[MAXN][MAXN]; } G , ans , tmp ;

void mul( matrx x , matrx y ) {
    for( int i = 1 ; i < MAXN ; ++ i )
        for( int j = 1 ; j < MAXN ; ++ j ) {
            tmp.a[i][j] = 0;
            for( int p = 1 ; p < MAXN ; ++ p )
                tmp.a[i][j] += x.a[i][p] * y.a[p][j] , tmp.a[i][j] %= P;
        }
}

void work( int k ) {
    while( k ) {
        if( k & 1 ) mul( ans , G ) , ans = tmp ;
        k >>= 1 , mul( G , G ) , G = tmp;
    }
}

int main() {
    cin >> n >> t;
    for( int i = 1 ; i <= n ; ++ i )
        for( int j = 1 ; j <= n ; ++ j ){
            scanf("%1d" , &G.a[i][j]);
            k = 1;
            while( G.a[i][j] > 1) G.a[i + (k-1) * n][i + k * n] = 1 , --G . a[i][j] , ++ k;
            if( G.a[i][j] ) G.a[i][j] = 0 , G.a[i + (k-1)*n][j] = 1;
        }
    for( int i = 1 ; i < MAXN ; ++ i ) ans.a[i][i] = 1;
    work( t );
    cout << ans.a[1][n];
}