AtCoder Grand Contest 031 D: A Sequence of Permutations

https://atcoder.jp/contests/agc031/tasks/agc031_d

This article is almost the same as the official editorial. I just want to write English and Chinese (A month has passed since I started learning Chinese. If you cannot read my Chinese, I'm sorry.)
我的说明和正式的说明很相像。我刚想写英文和中文。如果你不能理解我的中文，对不起。

The key idea is a permutation can be treated as a bijection. If we treat them as bijections, we can write f(a[n], a[n+1]) as a[n+1]a[n]^-1.
因为我们能吧全排列当做双射，所以 f(a[n],a[n+1]) 可以写成 a[n+1]a[n]^-1。

Then, let us make a list of a[n]. In this program, the inverse of p is denoted by P.
然后，枚举 a[n]。这个程序中 P 是 p 的逆元素。

def reduce(s)
  loop do
    t = s.gsub('pP', '')
         .gsub('Pp', '')
         .gsub('qQ', '')
         .gsub('Qq', '')
    break if s == t
    s = t
  end
  s
end

def inverse(f)
  f.reverse.swapcase
end

s = ['p', 'q']
(2..40).each do |i|
  s[i] = reduce(s[i - 1] + inverse(s[i - 2]))
end

s.each do |x|
  puts x
end

p
q
qP
qPQ
qPQpQ
qPQppQ
qPQpqpQ
qPQpqPqpQ
qPQpqPPqpQ
qPQpqPQPqpQ
qPQpqPQpQPqpQ
qPQpqPQppQPqpQ
qPQpqPQpqpQPqpQ
qPQpqPQpqPqpQPqpQ
qPQpqPQpqPPqpQPqpQ
qPQpqPQpqPQPqpQPqpQ
qPQpqPQpqPQpQPqpQPqpQ
qPQpqPQpqPQppQPqpQPqpQ
qPQpqPQpqPQpqpQPqpQPqpQ
qPQpqPQpqPQpqPqpQPqpQPqpQ
qPQpqPQpqPQpqPPqpQPqpQPqpQ
qPQpqPQpqPQpqPQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQpQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQppQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQpqpQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQpqPqpQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQpqPPqpQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQpqPQPqpQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQpqPQpQPqpQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQpqPQppQPqpQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQpqPQpqpQPqpQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQpqPQpqPqpQPqpQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQpqPQpqPPqpQPqpQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQpqPQpqPQPqpQPqpQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQpqPQpqPQpQPqpQPqpQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQpqPQpqPQppQPqpQPqpQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQpqPQpqPQpqpQPqpQPqpQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQpqPQpqPQpqPqpQPqpQPqpQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQpqPQpqPQpqPPqpQPqpQPqpQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQpqPQpqPQpqPQPqpQPqpQPqpQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQpqPQpqPQpqPQpQPqpQPqpQPqpQPqpQPqpQPqpQ

We can see that qPQp and PqpQ appears repeatedly, and this sequence has the period of length 6. The power of the bijection can be achieved by O(log n) times composition, thus this problem is solved.
我们可以看很多的 qPQp 和 PqpQ 在 a[i] 里。双射的幂能实现 O(N log N) 的复杂度。所以我们得到答案了。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define REP(i, n) for (int i = 0; i < (n); i++)

struct perm {
  vector<int> a;
  perm(int n) : a(n) {}
  int size() { return a.size(); }
  int &operator[](int k) { return a[k]; }
};

perm operator*(perm a, perm b) {
  const int n = a.size();
  perm ans(n);
  REP(i, n) ans[i] = a[b[i]];
  return ans;
}

perm inv(perm a) {
  const int n = a.size();
  perm ans(n);
  REP(i, n) ans[a[i]] = i;
  return ans;
}

perm pow(perm a, int b) {
  const int n = a.size();
  perm ans(n);
  REP(i, n) ans[i] = i;
  while (b > 0) {
    if (b & 1) ans = ans * a;
    a = a * a;
    b >>= 1;
  }
  return ans;
}

void print(perm a) {
  for (int i = 0; i < a.size(); i++) {
    if (i > 0) cout << ' ';
    cout << a[i] + 1;
  }
  cout << '\n';
}

int main() {
  int N, K;
  cin >> N >> K;
  perm P(N), Q(N);
  REP(i, N) cin >> P[i], P[i]--;
  REP(i, N) cin >> Q[i], Q[i]--;
  auto X = Q * inv(P) * inv(Q) * P;
  auto Y = inv(P) * Q * P * inv(Q);
  vector<perm> A;
  A.push_back(P);
  A.push_back(Q);
  for (int i = 0; i < 5; i++) {
    A.push_back(A[i + 1] * inv(A[i]));
  }
  A.erase(A.begin());
  if (K == 1) {
    print(P);
    return 0;
  }
  K -= 2;
  perm ans = pow(X, K / 6) * A[K % 6] * pow(Y, K / 6);
  print(ans);
}

I love this problem.
我喜欢这道题。