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 。
思路真是巧妙。
把每一个点都拆成9个。
然后矩阵快速幂。
#include#include #include #include #include using namespace std;#define reg register inline int read() { int res = 0;char ch=getchar();bool fu=0; while(!isdigit(ch)) { if(ch=='-')fu=1;ch=getchar();} while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch^48), ch=getchar(); return fu?-res:res;}#define mod 2009int n, T;struct Mat { int a[95][95]; Mat(){memset(a, 0, sizeof a);} inline void init() { for(int i=1;i<=90;i++)a[i][i]=1;} friend Mat operator * (Mat x, Mat y) { Mat z; for (reg int i = 1 ; i <= 90 ; i ++) for (reg int k = 1 ; k <= 90 ; k ++) for (reg int j = 1 ; j <= 90 ; j ++) z.a[i][j] = (z.a[i][j] + x.a[i][k] * y.a[k][j]) % mod; return z; } friend Mat operator ^ (Mat x, int y) { Mat res;res.init(); while(y) { if (y & 1) res = res * x; x = x * x; y >>= 1; } return res; }}A, ans;int id[99][99], tot;int main(){ n = read(), T = read(); for (reg int i = 1 ; i <= n ; i ++) { for (reg int j = 0 ; j <= 8 ; j ++) { id[i][j] = ++tot; if (j) A.a[tot-1][tot] = 1; } } for (reg int i = 1 ; i <= n ; i ++) { for (reg int j = 1 ; j <= n ; j ++) { int x; scanf("%1d", &x); if (x) A.a[id[i][x-1]][id[j][0]] = 1; } } A = A ^ T; printf("%d\n", A.a[id[1][0]][id[n][0]] % mod); return 0;}