Description

windy在有向图中迷路了。 该有向图有 N 个节点，windy从节点 0 出发，他必须恰好在 T 时刻到达节点 N-1。 现在给出该有向图，你能告诉windy总共有多少种不同的路径吗？ 注意：windy不能在某个节点逗留，且通过某有向边的时间严格为给定的时间。
Input

第一行包含两个整数，N T。 接下来有 N 行，每行一个长度为 N 的字符串。 第i行第j列为’0’表示从节点i到节点j没有边。 为’1’到’9’表示从节点i到节点j需要耗费的时间。
Output

包含一个整数，可能的路径数，这个数可能很大，只需输出这个数除以2009的余数。
Sample Input
【输入样例一】

2 2

11

00

【输入样例二】

5 30

12045

07105

47805

12024

12345

Sample Output
【输出样例一】

1

【样例解释一】

0->0->1

【输出样例二】

852

HINT

30%的数据，满足 2 <= N <= 5 ； 1 <= T <= 30 。 100%的数据，满足 2 <= N <= 10 ； 1 <= T <= 1000000000 。

解法：自己见得少，拿到这题思考了，没有什么思路。看了世界爷的博客，恍然大悟。

考虑当所有边权都是1的时候 那么显然邻接矩阵自乘T次之后a[1][n]就是答案

因为当边权为1的时候a[i][j]可以表示从第i个点转移到第j个点的方案数 显然这个符合矩乘的定义

现在边权最大为9 那么将一个点拆成9个 第i个点拆成的第j+1个点向第j个点连一条边权为1的边

那么i->j有一条边权为k的边等价于i向j拆成的第k个点连边

建好这个矩阵之后，跑一个矩阵幂就行了。

//BZOJ 1297

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

const int maxn = 100;
const int mod = 2009;
int n, m, t;
int getid(int i, int j){
    return (j-1)*m+i;
}

typedef struct node{
    int a[maxn][maxn];
}Matrix;

Matrix operator * (Matrix x, Matrix y){
    Matrix ans;
    for(int i=0; i<maxn; i++){
        for(int j=0; j<maxn; j++){
            ans.a[i][j]=0;
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            for(int k=1; k<=n; k++){
                ans.a[i][j] = (ans.a[i][j] + x.a[i][k]*y.a[k][j])%mod;
            }
        }
    }
    return ans;
}

Matrix pow(Matrix a, int n){
    Matrix res;
    for(int i=0; i<maxn; i++){
        for(int j=0; j<maxn; j++){
            if(i==j) res.a[i][j]=1;
            else res.a[i][j]=0;
        }
    }
    while(n){
        if(n&1) res = res*a;
        a = a*a;
        n>>=1;
    }
    return res;
}

int main()
{
    scanf("%d%d", &m,&t);
    n=9*m;
    Matrix aa;
    for(int i=0; i<maxn; i++){
        for(int j=0; j<maxn; j++){
            aa.a[i][j]=0;
        }
    }
    for(int i=1; i<=m; i++){
        for(int j=2; j<=9; j++){
            aa.a[getid(i,j)][getid(i,j-1)]=1;
        }
    }
    for(int i=1; i<=m; i++){
        for(int j=1; j<=m; j++){
            int x;
            scanf("%1d",&x);
            if(x==0) continue;
            aa.a[i][getid(j,x)]=1;
        }
    }
    Matrix ans = pow(aa, t);
    printf("%d\n", ans.a[1][m]);
    return 0;
}