loj10225迷路

原题来自：SCOI 2009

Windy 在有向图中迷路了。该有向图有 n 个节点，Windy 从节点 0 出发，他必须恰好在 t 时刻到达节点n-1 。

现在给出该有向图，你能告诉 Windy 总共有多少种不同的路径吗？

注意：Windy 不能在某个节点逗留，且通过某有向边的时间严格为给定的时间。

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

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

2 2
11
00

对于 100% 的数据，满足2<=n<=10,1<=t<=1e9 。

___________________________________

矩阵乘法没有什么技术含量，但是拆点的思想很需要学习。

怎么拆点可以参考下面的大神的博客！

https://blog.csdn.net/xf2056188203/article/details/108940321

___________________________________

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=105;
 4 struct node
 5 {
 6     int sz[maxn][maxn];
 7     node()
 8     {
 9         memset(sz,0,sizeof sz);
10     }
11 }p,st,s;
12 int n,t;
13 
14 node cheng(node a,node b)
15 {
16     node c;
17     for(int i=0;i<100;++i)
18         for(int j=0;j<100;++j)
19             for(int k=0;k<100;++k)
20                 c.sz[i][j]=(c.sz[i][j]+a.sz[i][k]*b.sz[k][j])%2009;
21     return c;
22 }
23 
24 node pwr(int n)
25 {
26     if(n==0)return st;
27     node tp=pwr(n/2);
28     node ans=cheng(tp,tp);
29     if(n%2)ans=cheng(ans,p);
30     return ans;
31 }
32 
33 int main()
34 {
35     scanf("%d%d",&n,&t);
36     for(int i=0;i<100;++i)st.sz[i][i]=1;
37     for(int i=0;i<n;++i)
38         for(int v,j=0;j<n;++j)
39         {
40             scanf("%1d",&v);
41             if(v)
42             {
43                 int tp=i;
44                 for(int k=0;k<v-1;++k)
45                 {
46                     p.sz[tp][tp+10]=1;
47 //                    cerr<<tp<<','<<tp+10<<endl;
48                     tp+=10;
49                 }
50                 p.sz[tp][j]=1;
51 //                cerr<<tp<<','<<j<<endl;
52 //                cerr<<"----------"<<endl;
53             }
54         }
55     node ans=pwr(t);
56     cout<<ans.sz[0][n-1]<<endl;
57     return 0;
58 }

View Code