HDU2157 （水题）状态转移

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2157

题目意思：给定0—n-1标号的图，求出s点到t点恰好经过k个点的方案数。

题目思路：状态转移。

 1 #include<iostream>
 2 #include<string.h>
 3 typedef long long ll;
 4 #define MOD 1000
 5 #define mod(x) ((x)%MOD)
 6 const int N = 22;
 7 using namespace std;
 8 struct mat{
 9     ll a[N][N];
10     mat()
11     {
12         memset(a,0,sizeof(a));
13     }
14     friend mat operator * (mat x,mat y)
15     {
16         mat ans;
17         for(int i = 0;i < N;i++)
18         {
19             for(int j = 0;j < N;j++)
20             {
21                 for(int k = 0;k < N;k++)
22                     ans.a[i][k] = mod(ans.a[i][k]+x.a[i][j] * y.a[j][k] % MOD);
23             }
24         }
25         return ans;
26     }
27     friend mat operator ^ (mat x,ll m)
28     {
29         mat unit;
30         for(int i = 0;i < N;i++) unit.a[i][i] = 1;
31         while(m)
32         {
33             if(m&1) unit = unit * x;
34             x = x * x;
35             m >>= 1;
36         }
37         return unit;
38     }
39 };
40 int main()
41 {
42     ll n,m,t,a,b,k,s,e;
43     while(cin>>n>>m)
44     {
45         if(!n&&!m) return 0;
46         mat ans,res;
47         for(int i = 1;i <= m;i++)
48         {
49             cin>>a>>b;
50             ans.a[a][b] = 1LL;
51         }
52         cin>>t;
53         while(t--)
54         {
55             ll sum = 0;
56             cin>>s>>e>>k;
57             res = ans ^ k;
58             cout<<res.a[s][e]%MOD<<endl;
59         }
60     }
61     return 0;
62 }