思路

首先,假设图中所有路径长度都为1.走步时从到的方案数,走步时从到的方案数.那么走步的方案数.
矩阵快速幂就OK了.
但是这里边权不为1.由于数据范围小,我们可以将边权为的边拆成条边权为1的边,然后矩阵快速幂即可.复杂度为

代码

#include<bits/stdc++.h>
using namespace std;
#define mod 2009

int a[1 << 7][1 << 7], ans[1 << 7][1 << 7], N, T, tot, t, c[1 << 7][1 << 7];

void mul( int a[1 << 7][1 << 7], int b[1 << 7][1 << 7] ){
    memset( c, 0, sizeof c );
    for ( int i = 1; i <= tot; ++i )
        for ( int k = 1; k <= tot; ++k )
            for ( int j = 1; j <= tot; ++j )
                c[i][j] = ( c[i][j] + a[i][k] * b[k][j] ) % mod;
}

int main(){
    scanf( "%d%d", &N, &T ); tot = N;
    for ( int i = 1; i <= N; ++i ){
        t = 1;
        for ( int j = 1; j <= N; ++j ){
            while( !isdigit( a[i][j] = getchar() ) );
            a[i][j] &= 15; t = max( t, a[i][j] );
            if ( a[i][j] > 1 ) a[tot + a[i][j] - 1][j] = 1, a[i][j] = 0;
        }
        if ( t > 1 ) a[i][tot + 1] = 1;
        for ( int j = tot + 2; j < tot + t; ++j ) a[j - 1][j] = 1;
        tot = t + tot - 1;
    }
    for ( int i = 1; i <= tot; ++i ) ans[i][i] = 1;
    for ( ; T; T >>= 1, mul( a, a ), memcpy( a, c, sizeof c ) ) if ( T & 1 ) mul( ans, a ), memcpy( ans, c, sizeof c );
    printf( "%d\n", ans[1][N] );
    return 0;
}