居酒屋からのエクストリーム参加。D 問題が面白そうだったので突っ込んだ。解けてよかった！！！

問題概要

$1$ から $N$ までの整数からなる 2 つの順列 $p, q$ に対して、新たな順列 $f(p, q)$ を以下のように定める:

$f(p, q)$ := $p_i$ 項目の値は $q_i$ である

今、順列の列を

$a_1 = p$
$a_2 = q$
$a_{n+2} = f(a_{n}, a_{n+1})$

で定める。正整数 $K$ が与えられるので $a_K$ を求めよ。

制約

$1 \le N \le 10^{5}$
$1 \le K \le 10^{9}$

考えたこと

順列を操作していくような問題では

逆順列も考えてみる
1 つの要素に着目してそれがどう動いて行くかを観察する
順列を写像だと思ってどうなるか

あたりが典型考察だと思う。今回は逆順列を考えても何も見えないし、1 つの要素に着目してみてもよくわからなかった。しかし写像だと思うとかなり視界が開けて来る。

まず $f$ の定義から $r = f(p, q)$ とおくと

$r(p(x)) = q(x)$

なことがわかるが、これはつまり $r = qp^{-1}$ であり、

$f(p, q) = qp^{-1}$

であることを表している！！！！！
ここまでわかると、 $a_{2}, a_{3}, \dots$ を順々に $p$ と $q$ で表せることがわかる。そして表せば何かが見えて来るのではないかという気持ちになる。

書いてみる

$a_{1} = p$
$a_{2} = q$
$a_{3} = qp^{-1}$
$a_{4} = qp^{-1}q^{-1}$
$a_{5} = qp^{-1}q^{-1}pq^{-1}$
$a_{6} = qp^{-1}q^{-1}ppq^{-1}$
$a_{7} = qp^{-1}q^{-1}pqpq^{-1}$
$a_{8} = qp^{-1}q^{-1}pqp^{-1}qpq^{-1}$
$a_{9} = qp^{-1}q^{-1}pqp^{-1}p^{-1}qpq^{-1}$
$a_{10} = qp^{-1}q^{-1}pqp^{-1}q^{-1}p^{-1}qpq^{-1}$
$a_{11} = qp^{-1}q^{-1}pqp^{-1}q^{-1}pq^{-1}p^{-1}qpq^{-1}$
$a_{12} = qp^{-1}q^{-1}pqp^{-1}q^{-1}ppq^{-1}p^{-1}qpq^{-1}$

何か見えるだろうか。。。
解説では周期 6 の構造を見出している。僕のは解答と少し違うかもしれないが、周期 3 の以下のような構造を見出した。

$r_{k} = p^{-1}q^{-1}pqp^{-1}q^{-1}pq \dots$ 　(項が $k$ 個)

のように $4$ 個ごとに規則性のある合成関数を定義したときに、

$a_{3k} = qr_{2k-1}r_{2k-3}^{-1}q^{-1}$
$a_{3k+1} = qr_{2k}r_{2k-3}^{-1}q^{-1}$
$a_{3k+2} = qr_{2k}r_{2k-1}^{-1}q^{-1}$

が成立する。この予想が立ったならば証明は難しくなくて、数学的帰納法で証明できる。なお証明では

$r_{2k}r_{2k-1}^{-1} = r_{2k+1}r_{2k-2}^{-1}$
$r_{2k-1}r_{2k-2}^{-1} = r_{2k}r_{2k-3}^{-1}$

といった関係を用いる。ここまでわかれば、一般に $r_{k}$ はダブリングを用いて $O(N \log{K})$ で計算することができる。全体を通して $O(N \log{K})$ で計算できる。

#include <iostream>
#include <vector>
using namespace std;

// 代表的関数
vector<int> idv, p, q, pi, qi; // pi, qi は p, q の逆写像, idv は恒等写像

// 逆写像計算
vector<int> inv(const vector<int> &v) {
    int N = v.size();
    vector<int> res(N);
    for (int i = 0; i < N; ++i) res[v[i]] = i;
    return res;
}

// 合成写像計算
inline vector<int> operator +(const vector<int> &a, const vector<int> &b) {
    int N = a.size();
    vector<int> res(N);
    for (int i = 0; i < N; ++i) res[i] = a[b[i]];
    return res;
}

// r_k
vector<vector<int> > beki; // beki[i] := r[4×2^i], 前計算しておく
vector<int> calc(long long k) {
    int num = k / 4;
    int r = k % 4;
    vector<int> amari = idv;
    if (r == 0) amari = idv;
    else if (r == 1) amari = pi;
    else if (r == 2) amari = pi + qi;
    else if (r == 3) amari = pi + qi + p;
    auto syuki = idv;
    for (int i = 0; i < 35; ++i) if (num & (1LL<<i)) syuki = syuki + beki[i];
    return syuki + amari;
}

// 解く
vector<int> solve(long long K) {
    if (K == 1) return p;
    if (K == 2) return q;
    if (K == 3) return q + pi;
    if (K == 4) return q + pi + qi;
    if (K == 5) return q + pi + qi + p + qi;
    if (K == 6) return q + pi + qi + p + p + qi;
    long long a, b;
    long long k = K / 3;
    if (K % 3 == 0) a = k*2-1, b = k*2-3;
    else if (K % 3 == 1) a = k*2, b = k*2-3;
    else a = k*2, b = k*2-1;
    auto res = q + calc(a) + inv(calc(b)) + qi;
    return res;
}

int main() {
    // 入力, 恒等写像, 逆写像
    int N, K; cin >> N >> K;
    idv.resize(N); p.resize(N); q.resize(N);
    for (int i = 0; i < N; ++i) idv[i] = i;
    for (int i = 0; i < N; ++i) cin >> p[i], --p[i];
    for (int i = 0; i < N; ++i) cin >> q[i], --q[i];
    pi = inv(p);
    qi = inv(q);

    // 繰り返し構造のダブリング前処理
    auto pqpq = pi + qi + p + q;
    beki.resize(35);
    beki[0] = pqpq;
    for (int i = 0; i+1 < 35; ++i) beki[i+1] = beki[i] + beki[i];

    // 解く
    auto res = solve(K);
    for (auto v : res) cout << v + 1 << " ";
    cout << endl;
}