Advertisement
Guest User

Untitled

a guest
Nov 28th, 2014
153
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.17 KB | None | 0 0
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <string>
  4. #include <cmath>
  5. #include <vector>
  6. #include <algorithm>
  7. #include <map>
  8. #include <set>
  9.  
  10. using namespace std;
  11.  
  12. #define forn(i,n) for(int i = 0; i < n; i++)
  13. #define ll long long
  14. #define ini(type, n) \
  15.         type n; \
  16.         cin >> n;
  17.  
  18. ll numbers_for_NOK(vector<int> &mul, ll cl)
  19. {
  20.     if (cl == 2 || cl == 3)
  21.     {
  22.         if (mul[cl] == 0)
  23.             mul[cl]++;
  24.         return 0;
  25.     }
  26.  
  27.     vector<int> mul_cl(mul.size());
  28.     for (int i = 2; i <= sqrt((double)cl); i++)
  29.     {
  30.         if (cl%i == 0)
  31.         {
  32.             cl /= i;
  33.             mul_cl[i]++;
  34.             if (mul[i] < mul_cl[i])
  35.             {
  36.                 mul[i] = mul_cl[i];
  37.             }
  38.         }
  39.     }
  40.     mul_cl[cl]++;
  41.     if (mul[cl] < mul_cl[cl])
  42.     {
  43.         mul[cl] = mul_cl[cl];
  44.     }
  45.  
  46.     return 0;
  47. }
  48.  
  49. ll NOK(vector<int> mul)
  50. {
  51.     ll nok = 1;
  52.     ll i = 2;
  53.     while (i < mul.size())
  54.     {
  55.         if (mul[i] != 0)
  56.         {
  57.             nok *= i;
  58.             mul[i]--;
  59.         }
  60.         else
  61.             i++;
  62.     }
  63.     return nok;
  64. }
  65.  
  66. ll making_power_short(vector<int> p, ll k, ll n)
  67. {
  68.     vector<bool> used(n);
  69.     vector<int> mul(n + 1);
  70.     forn(i, n)
  71.     {
  72.         if (!used[i])
  73.         {
  74.             ll cycle_length = 0;
  75.             ll j = i;
  76.             while (!used[j])
  77.             {
  78.                 cycle_length++;
  79.                 used[j] = true;
  80.                 j = p[j];
  81.             }
  82.             numbers_for_NOK(mul, cycle_length);
  83.         }
  84.     }
  85.     ll nok_cycles = NOK(mul);
  86.     return k%nok_cycles + !(k%nok_cycles)*nok_cycles;
  87. }
  88.  
  89. vector<int> modulo(const vector<int> p, ll k)
  90. {
  91.     vector<int> r;
  92.     forn(i, p.size())
  93.     {
  94.         r.push_back(p[(i + k) % p.size()]);
  95.     }
  96.     return r;
  97. }
  98.  
  99. vector<int> making_new_transposition(vector<int> p, ll k, ll n)
  100. {
  101.     vector<bool> used(n);
  102.     vector<int> result(n);
  103.     forn(i, n)
  104.     {
  105.         if (!used[i])
  106.         {
  107.             vector<int> cycle;
  108.             vector<int> add;
  109.             ll j = i;
  110.             while (!used[j])
  111.             {
  112.                 cycle.push_back(j);
  113.                 used[j] = true;
  114.                 j = p[j];
  115.                 add.push_back(j);
  116.             }
  117.            
  118.             add = modulo(add, k - 1);
  119.             forn(i, cycle.size())
  120.                 result[cycle[i]] = add[i];
  121.         }
  122.     }
  123.     return result;
  124. }
  125.  
  126.  
  127. int main()
  128. {
  129.     ini(ll, n);
  130.     ini(ll, k);
  131.     vector<int> p(n);
  132.     vector<int> q;
  133.     forn(i,n)
  134.     {
  135.         scanf("%d", &p[i]);
  136.     }
  137.  
  138.     ll mul = making_power_short(p, k, n);
  139.     q = making_new_transposition(p, mul, n);
  140.  
  141.     forn(i, n)
  142.     {
  143.         printf("%d ", q[i]);
  144.     }
  145.     cout << endl;
  146.     return 0;
  147. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement