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 。
Source
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
矩阵乘法优化DP~
首先，这是一道DP题，对于每一个点i，f[i][k]=sum(f[j][k-w[i][j]])，j、i相连，w[i][j]为边权，但是这样的话转移状态太多显然过不了……所以就去看了题解……
“首先有一个常识：如果没有路径长度的要求，且给定的邻接矩阵只有0和1表示通与不通的话，从S->E走N次的方案数就是这个矩阵自乘N次后的（S,E）的数值。”
（没有常识的小蒟蒻泪流满面……）
所以就构建出一个矩阵，用快速幂求解。
矩阵的构建方法是：
不同点连向同一点的边权可能不同，这样的话显然无法计数。我们发现边权从1到9，这暗示我们可以拆点。把每个点拆成9个点，每个点对应的9个点互相连边，然后点与点之间的边按照权值连向同一个点的不同分点。
然后就是重载运算符，快速幂求解了~
注意函数里开的矩阵要清零！
快速幂里的矩阵是0次方矩阵，对角线为1，其余均为0~
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define modd 2009 int n,t,tot;
char s[11]; struct node{ int a[101][101];
}a; node operator * (node u,node v)
{ node c; memset(c.a,0,sizeof(c.a)); for(int i=1;i<=tot;i++) for(int j=1;j<=tot;j++) for(int k=1;k<=tot;k++) c.a[i][j]=(c.a[i][j]+u.a[i][k]*v.a[k][j])%modd; return c;
} node mi(node u,int v)
{ node ans; for(int i=1;i<=tot;i++) ans.a[i][i]=1; while(v) { if(v&1) ans=ans*u; u=u*u;v>>=1; } return ans;
} int main()
{ scanf("%d%d",&n,&t);tot=n*9; for(int i=1;i<=n;i++) for(int j=1;j<=8;j++) a.a[(i-1)*9+j][(i-1)*9+j+1]=1; for(int i=1;i<=n;i++) { scanf("%s",s+1); for(int j=1;j<=n;j++) if(s[j]!='0') a.a[(i-1)*9+s[j]-'0'][(j-1)*9+1]=1; } a=mi(a,t); printf("%d\n",a.a[1][n*9-8]); return 0;
}