bzoj 1297: [SCOI2009]迷路

思路：首先我们先了解一个性质，对于一个邻接矩阵 edge 来说， (edge^t)[ i ][ j ] 表示走t次能从i 到 j 的路径条数，但是

这道题里面不是邻接矩阵，所以我们要拆点变成邻接矩阵然后矩阵快速幂。

 1 #include<bits/stdc++.h>
 2 #define LL long long
 3 #define ll long long
 4 #define fi first
 5 #define se second
 6 #define mk make_pair
 7 #define pii pair<int,int>
 8 #define piii pair<int, pair<int,int>>
 9 
10 using namespace std;
11 
12 const int N = 100 + 7;
13 const int inf = 0x3f3f3f3f;
14 const LL INF = 0x3f3f3f3f3f3f3f3f;
15 const int mod = 1e9 + 7;
16 const int Mod = 2009;
17 
18 struct Matrix
19 {
20     int r, c;
21     int a[N][N];
22     Matrix(int r = 0, int c = 0)
23     {
24         this -> r = r;
25         this -> c = c;
26         memset(a,0,sizeof(a));
27     }
28     void init()
29     {
30         for(int i=0;i<r;i++)
31             for(int j=0;j<c;j++)
32                 a[i][j]=(i==j);
33     }
34     Matrix operator * (const Matrix &B)const
35     {
36         Matrix C(r, c);
37         for(int i=0;i<r;i++)
38             for(int j=0;j<c;j++)
39                 for(int k=0;k<r;k++)
40                     C.a[i][j]=(C.a[i][j]+1LL*a[i][k]*B.a[k][j])%Mod;
41         return C;
42     }
43     Matrix operator ^ (const ll &p)const
44     {
45         Matrix A=(*this),res(r, c);
46         res.init();
47         ll t=p;
48         while(t)
49         {
50             if(t&1)res=res*A;
51             A=A*A;
52             t>>=1;
53         }
54         return res;
55     }
56 }M;
57 
58 
59 int n, t;
60 int main() {
61     scanf("%d%d", &n, &t);
62     M.r = M.c = 9 * n;
63     for(int i = 0; i < n * 9; i++)
64         if(i % 9 != 0) M.a[i - 1][i] = 1;
65 
66     for(int i = 0; i < n; i++) {
67         for(int j = 0; j < n; j++) {
68             int x; scanf("%1d", &x);
69             if(!x) continue;
70             M.a[i * 9 + x - 1][j * 9] = 1;
71         }
72     }
73 
74     M = M ^ t;
75 
76     printf("%d
", M.a[0][(n - 1) * 9]);
77     return 0;
78 }
79 
80 /*
81 */