けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder AGC 031 D - A Sequence of Permutations (1000 点)

居酒屋からのエクストリーム参加。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;
}