Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <iomanip>
- #include <string>
- #include <cmath>
- #include <vector>
- #include <algorithm>
- #include <map>
- #include <set>
- using namespace std;
- #define forn(i,n) for(int i = 0; i < n; i++)
- #define ll long long
- #define ini(type, n) \
- type n; \
- cin >> n;
- ll numbers_for_NOK(vector<int> &mul, ll cl)
- {
- if (cl == 2 || cl == 3)
- {
- if (mul[cl] == 0)
- mul[cl]++;
- return 0;
- }
- vector<int> mul_cl(mul.size());
- for (int i = 2; i <= sqrt((double)cl); i++)
- {
- if (cl%i == 0)
- {
- cl /= i;
- mul_cl[i]++;
- if (mul[i] < mul_cl[i])
- {
- mul[i] = mul_cl[i];
- }
- }
- }
- mul_cl[cl]++;
- if (mul[cl] < mul_cl[cl])
- {
- mul[cl] = mul_cl[cl];
- }
- return 0;
- }
- ll NOK(vector<int> mul)
- {
- ll nok = 1;
- ll i = 2;
- while (i < mul.size())
- {
- if (mul[i] != 0)
- {
- nok *= i;
- mul[i]--;
- }
- else
- i++;
- }
- return nok;
- }
- ll making_power_short(vector<int> p, ll k, ll n)
- {
- vector<bool> used(n);
- vector<int> mul(n + 1);
- forn(i, n)
- {
- if (!used[i])
- {
- ll cycle_length = 0;
- ll j = i;
- while (!used[j])
- {
- cycle_length++;
- used[j] = true;
- j = p[j];
- }
- numbers_for_NOK(mul, cycle_length);
- }
- }
- ll nok_cycles = NOK(mul);
- return k%nok_cycles + !(k%nok_cycles)*nok_cycles;
- }
- vector<int> modulo(const vector<int> p, ll k)
- {
- vector<int> r;
- forn(i, p.size())
- {
- r.push_back(p[(i + k) % p.size()]);
- }
- return r;
- }
- vector<int> making_new_transposition(vector<int> p, ll k, ll n)
- {
- vector<bool> used(n);
- vector<int> result(n);
- forn(i, n)
- {
- if (!used[i])
- {
- vector<int> cycle;
- vector<int> add;
- ll j = i;
- while (!used[j])
- {
- cycle.push_back(j);
- used[j] = true;
- j = p[j];
- add.push_back(j);
- }
- add = modulo(add, k - 1);
- forn(i, cycle.size())
- result[cycle[i]] = add[i];
- }
- }
- return result;
- }
- int main()
- {
- ini(ll, n);
- ini(ll, k);
- vector<int> p(n);
- vector<int> q;
- forn(i,n)
- {
- scanf("%d", &p[i]);
- }
- ll mul = making_power_short(p, k, n);
- q = making_new_transposition(p, mul, n);
- forn(i, n)
- {
- printf("%d ", q[i]);
- }
- cout << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement