SHARE
TWEET

Untitled

a guest Apr 19th, 2019 80 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 <cmath>
  5. #include <list>
  6. #include <stack>
  7. #include <deque>
  8. #include <bitset>
  9. #include <set>
  10. using namespace std;
  11. typedef long long ll;
  12. const ll MOD1 = 1e9 + 7;
  13. ll ans = 1;
  14. ll n, k, kmin, cycle;
  15. bool ch;
  16. vector<int> g[1000001];
  17. int pred[1000001];
  18. int main() {
  19.     bitset<1000001>vis;
  20.     int i, j;
  21.     cin >> n >> k;
  22.     int x;
  23.     for (i = 1; i <= n; i++) {
  24.         cin >> x;
  25.         if (x != i) {
  26.             g[i].push_back(x);
  27.             g[x].push_back(i);
  28.         }
  29.     }
  30.     ll temp;
  31.     int cur;
  32.     int t;
  33.     stack<int>st;
  34.     for (i = 1; i <= n; i++) {
  35.         if (!vis[i]) {
  36.             ch = false;
  37.             temp = 1;
  38.             cycle = 0;
  39.             kmin = 0;
  40.             st.push(i);
  41.             while (!st.empty()) {
  42.                 cur = st.top();
  43.                 st.pop();
  44.                 if (!vis[cur]) {
  45.                     kmin++;
  46.                     vis[cur] = true;
  47.                     for (auto y : g[cur]) {
  48.                         if(y!=pred[cur])
  49.                         pred[y] = cur;
  50.                         if (!vis[y]) {
  51.                             st.push(y);
  52.                         }
  53.                         else if (!ch && vis[y] && y != pred[cur]) {
  54.                             t = 0;
  55.                             ch = true;
  56.                             while (cur != y) {
  57.                                 cur = pred[cur];
  58.                                 t++;
  59.                             }
  60.                             cycle = t + 1;
  61.                             kmin -= (t + 1);
  62.                         }
  63.                     }
  64.                 }
  65.             }
  66.             if (cycle) {
  67.                 for (j = 0; j < cycle; j++) {
  68.                     temp = ((temp%MOD1)*((k - 1) % MOD1)) % MOD1;
  69.                 }
  70.                 if (cycle % 2 == 0) {
  71.                     temp += k - 1;
  72.                 }
  73.                 else {
  74.                     temp -= (k - 1);
  75.                 }
  76.                 if (temp < 0) {
  77.                     temp += MOD1;
  78.                 }
  79.                 temp %= MOD1;
  80.                 for (j = 0; j < kmin; j++) {
  81.                     temp = ((temp%MOD1)*((k - 1) % MOD1)) % MOD1;
  82.                 }
  83.             }
  84.             else {
  85.                 temp = ((temp%MOD1)*((k) % MOD1)) % MOD1;
  86.                 for (j = 0; j < kmin - 1; j++) {
  87.                     temp = ((temp%MOD1)*((k - 1)%MOD1))%MOD1;
  88.                 }
  89.             }
  90.             ans = ((temp%MOD1)*((ans) % MOD1)) % MOD1;
  91.         }
  92.     }
  93.     cout << ans;
  94.     //system("pause>nul");
  95.     return 0;
  96. }
  97. /*
  98. 12 3
  99. 7 7 10 6 2 3 5 1 9 4 11 11
  100. */
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top