第四周 2.7-2.13

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 typedef long long LL;
 6 const LL mod = 1e9 + 7;
 7 int N, K, tmp, G[101][101], dep[101];
 8 LL a[101], ans;
 9 
10 void dfs(int p, int d)
11 {
12     if(dep[p])
13     {
14         if(dep[p] == -1) return;
15         tmp += d - dep[p];
16         if(!ans) ans += a[d-dep[p]];
17         else ans = ans * a[d-dep[p]] % mod;
18         return;
19     }
20     dep[p] = d;
21     for(int i = 0; i < N; i++)
22     {
23         if(!G[p][i]) continue;
24         dfs(i, d + 1);
25     }
26     dep[p] = -1;
27 }
28 
29 int main(void)
30 {
31     int T;
32     scanf("%d", &T);
33     while(T--)
34     {
35         scanf("%d %d", &N, &K);
36         memset(G, 0, sizeof(G));
37         for(int i = 0; i < N; i++)
38         {
39             int to;
40             scanf("%d", &to);
41             G[i][to] = 1;
42         }
43         a[2] = K * (K - 1), a[3] = a[2] * (K - 2);
44         for(int i = 4; i <= N; i++)
45             a[i] = ( a[i-2] * (K - 1) + a[i-1] * (K - 2) ) % mod;
46         ans = 0LL, tmp = 0;
47         memset(dep, 0, sizeof(dep));
48         for(int i = 0; i < N; i++) dfs(i, 1);
49         for(int i = tmp; i < N; i++) ans = ans * (K - 1) % mod;
50         printf("%I64d\n", ans);
51     }
52     return 0;
53 }