windy在有向图中迷路了。 该有向图有 N 个节点，windy从节点 0 出发，他必须恰好在 T 时刻到达节点 N-1。 现在给出该有向图，你能告诉windy总共有多少种不同的路径吗？ 注意：windy不能在某个节点逗留，且通过某有向边的时间严格为给定的时间。
第一行包含两个整数，N T。 接下来有 N 行，每行一个长度为 N 的字符串。 第i行第j列为‘0‘表示从节点i到节点j没有边。 为‘1‘到‘9‘表示从节点i到节点j需要耗费的时间。
输出格式：
包含一个整数，可能的路径数，这个数可能很大，只需输出这个数除以2009的余数。
【样例解释一】
0->0->1
【数据范围】
30%的数据，满足 2 <= N <= 5 ； 1 <= T <= 30 。
100%的数据，满足 2 <= N <= 10 ； 1 <= T <= 1000000000 。
思路
一道有难度的矩阵乘法的题
时间长短和路径条数多少之间很显然有点矛盾，我们只能处理每一条路的同学时间都为1的，这样也可以说明从第i个点到第j个点之间的路径条数为1
设$a_{x}[i][j]$表示x分钟从第i个点到第j个点的路径条数
根据Floyd，我们知道$a_{x}[i][j]=\sum\limits_{k=1}^{n} a_{x-1}[i][k]*a_{x-1}[k][j] % mod$
结果就是$a_{t}[1][n]$
这样我们顺利的解决了（0/1）图
由于时间最大为9，所以我们完全可以把一个点拆成9个点，然后每两个点之间的边权为0或1
然后我们就$成功$的做完了这道题
CODE:
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; int t,n,a[101][101],ans[101][101],zlk[101][101],sum,mod=2009; void ksm(){ while(t){ if(t&1){ memset(zlk,0,sizeof(zlk)); rep(i,1,9*n) rep(j,1,9*n) rep(k,1,9*n) zlk[i][j]+=ans[i][k]*a[k][j],zlk[i][j]%=mod; rep(i,1,9*n) rep(j,1,9*n) ans[i][j]=zlk[i][j]; } memset(zlk,0,sizeof(zlk)); rep(i,1,9*n) rep(j,1,9*n) rep(k,1,9*n) zlk[i][j]+=a[i][k]*a[k][j],zlk[i][j]%=mod; rep(i,1,9*n) rep(j,1,9*n) a[i][j]=zlk[i][j]; t>>=1; } } int main(){ scanf("%d%d",&n,&t); rep(i,1,n){ char ch=getchar(); while(ch<‘0‘ || ch>‘9‘) ch=getchar(); rep(j,1,n){ int z=ch-‘0‘;ch=getchar(); if(!z) continue; rep(k,1,z-1) a[(i-1)*9+k][(i-1)*9+k+1]=1; a[(i-1)*9+z][(j-1)*9+1]=1; } } rep(i,1,n*9) ans[i][i]=1; ksm(); printf("%d",ans[1][n*9-8]); return 0; }
原文：https://www.cnblogs.com/handsome-zlk/p/10538882.html