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 。
分析：
30%
直接暴力dp
100%
矩阵优化的暴力dp
方程：
f[i][j]表示i时刻，到达j的方案数
f[i+t][k]+=f[i][j] (j,k联通，路径的权值是t)
这一次的路径有权值，这就不能直接用邻接矩阵来代替转移矩阵了
但是仔细观察一下，会发现每条边的权值不超过9
最多有10个点，
一下想到了拆点（虽然当时没有浮现这个词，但是已经想到了把一个点变成好几个，每个点代表不同的转移时间）
也就是说，我们的矩阵大概是有100*100
我们把每一个点拆成9个
如果x到y有一条2的边
那么连接x2—>y1，边权为1
在同一个点拆出的9个点中xi-1向xi连接边权为1的边
注意
如果读入的矩阵[i][i]=x
那么就从这个点分出来的第x个点连向第一个点
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
{
if (!mp[i][j]) continue;
int f1=(i-1)*9;
int f2=(j-1)*9;
H.H[f1+mp[i][j]][f2+1]=1;
}
for (int i=1;i<=n;i++)
for (int j=2;j<=9;j++)
H.H[(i-1)*9+j-1][(i-1)*9+j]=1;最后答案：
H[1][(n-1)*9+1]
这时第一行就是f[T],我们的目标是第n个点拆出来的第一个点，
（第n个点拆出来的第x个点（x！=1），对应的行走时间是T+x-1）
tip
这次是自乘T次
（这就让我得出了一个结论，T+1，T，T-1试一试就好了）
因为这次矩阵记录的是初始状态，一步都没有走
每次乘出来答案不对，我都以为是我的矩乘写错了
后来才发现是我的次数计算错了
//这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int INF=1e9+1;
const int p=2009;
int n,T,mp[10][10],f[20],S;
char s[10];
struct node{
int H[100][100];
node operator *(const node &a) const
{
node ans;
for (int i=1;i<=S;i++)
for (int j=1;j<=S;j++)
{
ans.H[i][j]=0;
for (int k=1;k<=S;k++)
ans.H[i][j]=(ans.H[i][j]+H[i][k]*a.H[k][j]%p)%p;
}
return ans;
}
void clear()
{
memset(H,0,sizeof(H));
}
node KSM(int pp)
{
node ans=(*this),a=(*this);
pp--;
while (pp)
{
if (pp&1)
ans=ans*a;
a=a*a;
pp>>=1;
}
return ans;
}
};
node H,ans;
void build()
{
int i,j;
H.clear();
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
{
if (!mp[i][j]) continue;
int f1=(i-1)*9;
int f2=(j-1)*9;
H.H[f1+mp[i][j]][f2+1]=1;
}
for (int i=1;i<=n;i++)
for (int j=2;j<=9;j++)
H.H[(i-1)*9+j-1][(i-1)*9+j]=1;
}
int main()
{
scanf("%d%d",&n,&T);
for (int i=1;i<=n;i++)
{
scanf("%s",s+1);
for (int j=1;j<=n;j++)
mp[i][j]=s[j]-'0';
}
build();
S=n*9;
ans=H.KSM(T);
printf("%d",ans.H[1][(n-1)*9+1]%p);
return 0;
}