引言

好题一道，恶心到爆。。。

---

迷路

题目描述

windy在有向图中迷路了。 该有向图有 N 个节点，windy从节点 0 出发，他必须恰好在 T 时刻到达节点 N-1。 现在给出该有向图，你能告诉windy总共有多少种不同的路径吗？ 注意：windy不能在某个节点逗留，且通过某有向边的时间严格为给定的时间。

输入输出格式

输入格式：

 

第一行包含两个整数，N T。 接下来有 N 行，每行一个长度为 N 的字符串。 第i行第j列为'0'表示从节点i到节点j没有边。 为'1'到'9'表示从节点i到节点j需要耗费的时间。

 

输出格式：

 

包含一个整数，可能的路径数，这个数可能很大，只需输出这个数除以2009的余数。

 

输入输出样例

输入样例#1： 复制

2 2
11
00

输出样例#1： 复制

1

输入样例#2： 复制

5 30
12045
07105
47805
12024
12345

输出样例#2： 复制

852

说明

【样例解释一】

0->0->1

【数据范围】

30%的数据，满足 2 <= N <= 5 ； 1 <= T <= 30 。

100%的数据，满足 2 <= N <= 10 ； 1 <= T <= 1000000000 。

---

思路详解

看到这一道题和他的数据就会发现，这是一道好题。

先对样例来一波分析，有两个点，1 和 2 

其邻接矩阵，其中点1自身有自环，那么让这个矩阵自乘会怎样呢?矩阵自乘后为，没有用换一种想法

T=1, 点1 到 点1 有一种方法，点1 到 点2 有一种方法，有点牵强

换一组数据 n = 3 ，T = 2 ，邻接矩阵（点3 有自环）

自乘一遍后得

点1 到 点2 ，再回到点1；点1 到 点3 ，再回到点1，有 2 种方法

而由点1 到点2 只有点1——点3——点2 一种方法

有点1 到 点3 则有 2 种方法（剩下的自己可以去推一推）

那么得到的结论就是这个矩阵的T幂次方后的矩阵的第 i 行 j 列元素表示 i 到 j 的方法总数（有点绕）

但这个图（初始矩阵）的边权为 1 ，如果为其他的数呢？

这个就要对图进行拆点（拆点详解），再对拆点后的图（矩阵）进行幂次方，这道题就解决了

---

代码

理解。。。消化。。。。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
  
int N , M , maxl ;
char a[107][107] ;
struct squr{
    int n , m ; 
    int b[107][107] ;
    squr() {
        memset( b , 0 , sizeof(b) ); 
    }
    squr operator * ( squr x ) {
        squr z ;
        z.n = n ;
        z.m = x.m ;
        for(int i = 1 ; i <= n ; ++ i ) 
            for(int j = 1 ; j <= z.m ; ++ j )
                for(int k = 1 ; k <= m ; ++ k )
                    z.b[i][j] = ( z.b[i][j] + b[i][k]*x.b[k][j] % 2009 ) % 2009;
        return z ;
    } //矩阵乘法 
};
  
int rep( int x , int y ) {
    return maxl*(x-1) + y ;
}
  
squr quick_pow( squr x , int y )//矩阵快速幂 
{
    squr sum ;
    sum.m = sum.n = N ;
    for(int i = 1 ; i <= sum.n ; ++ i ) sum.b[i][i] = 1 ;
    while( y > 0 ) {
        if( y %2 == 1 )
            sum = sum * x ;
        x = x *x ;
        y /= 2 ;
    }
    return sum ;
}
  
int main()
{
    squr B ;
    scanf("%d%d", &N , &M );
    for(int i = 1 ; i <= N ; ++ i ) {
        scanf("\n");
        for(int j = 1 ; j <= N ; ++ j ) {
            scanf("%c", &a[i][j] );
            maxl = max( maxl , a[i][j]-'0' );
        }
    }
    for(int i = 1 ; i <= N ; ++ i ) {
        for(int j = 1 ; j < maxl ; ++ j )
            B.b[ rep( i,j ) ][ rep( i,j+1 ) ] = 1 ;
        for(int j = 1 ; j <= N ; ++ j ) {
            if( a[i][j]-'0' != 0 )
                B.b[ rep( i,a[i][j]-'0' )][ rep( j,1 )] = 1 ;
        }
    }//拆点 
    N *= maxl;
    B.m = B.n = N ;
    B = quick_pow( B , M );
    printf("%d", B.b[1][N - maxl + 1] );
    return 0;
}