2020牛客多校第二场 J

题意：

给定序列长度n，已知原排列为${1， 2， 3， 4，... ，n}$，将它置换$k$次后得到序列$a$，问将它置换一次的序列是什么

思路：

首先找出序列中所有轮换，每一个轮换即为一个环，长度记为$len$。显而易见$A$序列为环置换$k % len$次的结果，而最终答案为每个环置换一次的结果，即置换$len * y + 1$次的结果（$y$未知）。

可令一次操作置换$t = k % len$次，设进行$x$次操作会得到最终结果。

由此可推出$ t * x = y * len + 1$，即$ t * x + len * y = 1$，欧几里得对$x$求最小正整数解即可。

  1 #pragma GCC optimize(3)
  2 #pragma GCC optimize(2)
  3 #include <map>
  4 #include <set>
  5 #include <array>
  6 #include <queue>
  7 #include <stack>
  8 #include <vector>
  9 #include <cstdio>
 10 #include <cstring>
 11 #include <sstream>
 12 #include <iostream>
 13 #include <stdlib.h>
 14 #include <algorithm>
 15 #include <unordered_map>
 16 
 17 using namespace std;
 18 
 19 typedef long long ll;
 20 typedef pair<int, int> PII;
 21 
 22 #define Time (double)clock() / CLOCKS_PER_SEC
 23 
 24 #define sd(a) scanf("%d", &a)
 25 #define sdd(a, b) scanf("%d%d", &a, &b)
 26 #define slld(a) scanf("%lld", &a)
 27 #define slldd(a, b) scanf("%lld%lld", &a, &b)
 28 
 29 const int N = 1e5 + 10;
 30 const int mod = 998244353;
 31 
 32 ll gcd(ll a, ll b)
 33 {
 34     return b ? gcd(b, a % b) : a;
 35 }
 36 
 37 ll exgcd(ll a, ll b, ll &x, ll &y)
 38 {
 39     if (!b)
 40     {
 41         x = 1;
 42         y = 0;
 43         return a;
 44     }
 45     int d = exgcd(b, a % b, y, x);
 46     y -= (a / b) * x;
 47     return d;
 48 }
 49 
 50 int n;
 51 ll k;
 52 ll a[N], vis[N];
 53 vector<int> v;
 54 
 55 int main()
 56 {
 57 #ifdef ONLINE_JUDGE
 58 #else
 59     freopen("/home/jungu/code/in.txt", "r", stdin);
 60     // freopen("/home/jungu/code/out1.txt", "w", stdout);
 61     // freopen("/home/jungu/code/out.txt","w",stdout);
 62 #endif
 63     ios::sync_with_stdio(false);
 64     cin.tie(0), cout.tie(0);
 65 
 66     cin >> n >> k;
 67 
 68     for (int i = 1; i <= n; i++)
 69     {
 70         cin >> a[i];
 71     }
 72 
 73     ll len = 0;
 74 
 75     for (int i = 1; i <= n; i++)
 76     {
 77 
 78         if (!vis[i])
 79         {
 80             v.clear();
 81             int j = i;
 82             while (!vis[j])
 83             {
 84                 vis[j] = 1;
 85                 v.push_back(j);
 86                 j = a[j];
 87             }
 88             len = (int) v.size();
 89             ll mid, c;
 90             ll g = exgcd(k, len, mid, c);
 91             mid = (mid % len + len) % len;
 92             for (int j = 0; j < len; j++)
 93             {
 94                 a[v[j]] = v[(mid + j) % len];
 95             }
 96         }
 97     }
 98 
 99     for (int i = 1; i <= n; i++)
100     {
101         cout << a[i] << " ";
102     }
103     cout << endl;
104 
105     return 0;
106 }

2020牛客多校 第二场 J

2020牛客多校第二场 J