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 。
题解
这题一眼就是矩阵乘法吧。。因为T那么大
但是矩乘一次只能处理边权为1的情况
怎么办？
观察一下边权，发现是1~9。那么一个点可以拆成9个点，拆成的点i-1向i连边，边权就为1了
于是一条边的两个点，可以从左边的拆点1连向右边的拆点i，i为边权
跑矩乘即可
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
const int mod=2009;
struct matrix
{int m[110][110];matrix(){memset(m,0,sizeof(m));}
}tmp;
matrix multi(matrix u,matrix v,int n,int m,int p)
{matrix ret;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)for(int k=1;k<=p;k++)ret.m[i][k]=(ret.m[i][k]+u.m[i][j]*v.m[j][k])%mod;return ret;
}
int n,t;
matrix pow_mod(matrix u,int b)
{matrix ans;for(int i=1;i<=n*9;i++)ans.m[i][i]=1;while(b){if(b%2==1)ans=multi(ans,u,9*n,9*n,9*n);u=multi(u,u,n*9,n*9,n*9);b/=2;}return ans;
}
char ss[110];
int main()
{scanf("%d%d",&n,&t);for(int i=1;i<=n;i++)for(int j=2;j<=9;j++)tmp.m[(i-1)*9+j][(i-1)*9+j-1]=1;for(int i=1;i<=n;i++){scanf("%s",ss+1);for(int j=1;j<=n;j++)if(ss[j]!='0')tmp.m[(i-1)*9+1][(j-1)*9+ss[j]-'0']=1;}tmp=pow_mod(tmp,t);printf("%d\n",tmp.m[1][(n-1)*9+1]);return 0;
}