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 。

 

这个题的思路真的妙啊……

主要还是我的问题，对矩阵乘法和邻接矩阵理解不够

有一个很重要的事情：邻接矩阵只有在边权为1的时候才能用矩乘！

而我却没有认真阅读数据范围，想当然的把原邻接矩阵做了矩乘

其实正解也近乎裸题

因为两点间若能到达，距离必定为1~9

那么我们就把一个点化为9个点

例如点1化为1~9点

点2化为10~18点

…………

样例便如下

1→2→3→4→5→6→7→8→9

 ↘

  10

最后R.a[1][10]即为所求结果

 

1 #include
     
       2 #include
      
        3 #include
       
         4 #define MOD (2009) 5 using namespace std; 6 struct Mar 7 { 8     int a[201][201]; 9 }R,unit;10 int n,t;11 Mar Mul(Mar A,Mar B)12 {13     Mar C;14     memset(C.a,0,sizeof(C.a));15     for (int i=1;i<=n;++i)16         for (int j=1;j<=n;++j)17             for (int k=1;k<=n;++k)18                 C.a[i][j]=(C.a[i][j]+A.a[i][k]*B.a[k][j])%MOD;19     return C;20 }21 22 Mar Mar_pow(Mar A,int p)23 {24     Mar ans=unit;25     while (p!=0)26     {27         if (p&1)28             ans=Mul(ans,A);29         p>>=1;30         A=Mul(A,A);31     }32     return ans;33 }34 int main()35 {36     char st[1001];37     scanf("%d%d",&n,&t);38     for (int i=1;i<=n*9;++i) unit.a[i][i]=1;39     for (int i=1;i<=n;++i)40     {41         scanf("%s",&st);42         for (int j=1;j<=n;++j)43         {44             int len=st[j-1]-48;45             if (len==0) continue;46             R.a[i*9-8+len-1][j*9-8]=1;47         }48     }49     for (int i=1;i<=n;++i)50         for (int j=1;j<=8;++j)51             R.a[i*9-9+j][i*9-9+j+1]=1;52     n*=9;53     R=Mar_pow(R,t);54     55     printf("%d",R.a[1][n-8]);56 }