Guest User

Untitled

a guest
Feb 26th, 2018
118
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <climits>
  5. #include <stdio.h>
  6. #include <queue>
  7. #include <set>
  8. #include <list>
  9. #include <cmath>
  10. #include <assert.h>
  11. #include <bitset>
  12. #include <cstring>
  13. #include <map>
  14. #include <iomanip> //cout << setprecision(node) << fixed << num
  15. #include <stack>
  16. #include <sstream>
  17.  
  18. #define all(x) x.begin(), x.end()
  19. #define pb push_back
  20. #define mp make_pair
  21. #define fi first
  22. #define se second
  23. #define print(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout << *it << " "; cout << endl;
  24. #define debug(x) cout << x << endl;
  25. #define debug2(x,y) cout << x << " " << y << endl;
  26. #define debug3(x,y,z) cout << x << " " << y << " " << z << endl;
  27.  
  28. typedef long long int ll;
  29. typedef long double ld;
  30. typedef unsigned long long int ull;
  31. typedef std::pair <int, int> ii;
  32. typedef std::vector <int> vi;
  33. typedef std::vector <ll> vll;
  34. typedef std::vector <ld> vld;
  35.  
  36. const int INF = int(1e9);
  37. const ll INF64 = ll(1e18);
  38. const ld EPS = 1e-9, PI = 3.1415926535897932384626433832795;
  39. using namespace std;
  40.  
  41. const int maxn = 107, maxk = 1007, mod = (int) 1e9 + 7;
  42. int N = 0, K, C[maxn];
  43. ll dp[maxn][2];
  44. set <int> graph[maxn];
  45. bitset <maxn> visited;
  46.  
  47. int cycle_st, cycle_en;
  48. void dfs(int node, int par) {
  49.     visited[node] = true;
  50.     for (int adj : graph[node]) {
  51.         if (adj != par) {
  52.             if (visited[adj]) {
  53.                 if (cycle_st != -1) continue;
  54.                 cycle_st = adj;
  55.                 cycle_en = node;
  56.             }
  57.             else {
  58.                 dfs(adj, node);
  59.             }
  60.         }
  61.     }
  62. }
  63. void rec(int n, int par) {
  64.     dp[n][0] = dp[n][1] = 1;
  65.     for (int adj : graph[n]) {
  66.         if (adj == par) continue;
  67.         if (n == cycle_st && adj == cycle_en) continue;
  68.         if (adj == cycle_st) {
  69.             dp[n][1] *= 0;
  70.         }
  71.         else {
  72.             rec(adj, n);
  73.             dp[n][0] *= (((((dp[adj][0] * (K-2)) % mod) + dp[adj][1])) % mod);
  74.             dp[n][0] %= mod;
  75.             dp[n][1] *= (((dp[adj][0]) * (K-1)) % mod);
  76.             dp[n][1] %= mod;
  77.         }
  78.     }
  79. }
  80.  
  81. int main() {
  82.     int T;
  83.     scanf("%d", &T);
  84.     while (T--) {
  85.         for (int i = 0; i < N; i++) {
  86.             graph[i].clear();
  87.         }
  88.         scanf("%d %d", &N, &K);
  89.         for (int i = 0; i < N; i++) {
  90.             scanf("%d", &C[i]);
  91.             graph[i].insert(C[i]);
  92.             graph[C[i]].insert(i);
  93.         }
  94.         visited.reset();
  95.         ll ans = 1;
  96.         for (int i = 0; i < N; i++) {
  97.             if (!visited[i]) {
  98.                 //find all connected components
  99.                 cycle_st = cycle_en = -1;
  100.                 dfs(i, -1);
  101.                 if (cycle_st == -1)
  102.                     cycle_st = i;
  103.                 rec(cycle_st, -1);
  104.                 ans *= ((dp[cycle_st][1] * K) % mod);
  105.                 ans %= mod;
  106.             }
  107.         }
  108.         assert(ans >= 0);
  109.         printf("%lld\n", ans);
  110.     }
  111. }
  112. /*
  113. 3
  114. 2 3
  115. 1 0
  116. ->3
  117. 4 3
  118. 1 2 3 0
  119. ->18
  120. 6 3
  121. 1 2 3 4 5 0
  122. ->66
  123. */
RAW Paste Data