置換の冪乗 - 忘れても大丈夫

問題. ABC013 D：阿弥陀

$n$ 本の縦線と $m$ 本の横線からなるあみだくじが与えられる．このあみだくじを縦に $d$ 個つなげる．左から $i \,(1 \le i \le n)$ 番目の縦線を選んであみたくじを行ったときの結果が下端で左から何番目にあるのかを答えよ．
制約： $2 \le n \le 10^5$ ，　 $0 \le m \le 2 \times 10^5$ ，　 $1 \le d \le 10^9$

あみだくじと置換の関係

ここを参考に説明をする．

集合 $N = \{1, 2, \ldots, n\}$ に対して， $N$ から $N$ への全単射を置換と呼ぶ．写像 $f \colon N \to N$ を左から $i$ 番目の縦線を選んであみだくじを行ったときの結果が左から $f(i)$ 番目であると定義すると $f$ は置換である．すなわち，任意のあみだくじに対してある置換が唯一に存在する．ただし，任意の置換に対してその置換を構成するようなあみだくじは複数ありうるので注意が必要である（しかし，横線の数の偶奇は一致：互換の数の偶奇性）．
$N$ 上の置換全体は写像の合成を演算子として群をなしており 対称群 と呼ばれている．また， $N$ 上の置換を集めた集合も群をなしており 置換群 と呼ばれている．ここで，与えられたあみだくじに対応する置換を $f$ とする． $f$ は恒等置換から始めて上から順番に横線 $(i, i + 1)$ に対して $f(i)$ と $f(i + 1)$ を交換することによって構成できる（隣接互換の積）．求める答えは置換群の言葉で言うと $f^d$ を求めることである．

解法1. 冪乗法

$f^d$ を求めるのに冪乗法を使用する．ちなみに，冪乗法は結合法則を満たせば使用できる（群は定義より満たす）． $f$ を構成するのに $O(m)$ 時間，2つの置換の積を計算するのに $O(n)$ 時間で， $f^d$ を計算するときの積の回数は冪乗法を用いて $O(\log d)$ 回である．したがって，全体で $O(m + n \log d)$ 時間で答えを求めることができる．

計算時間： $O(m + n \log d)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

// x = x * y
void multiple(vector<int> &x, const vector<int> &y) {
    const int n = x.size();
    vector<int> res(n);
    for (int i = 0; i < n; ++i) res[i] = x[y[i]];
    x = move(res);
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    int n, m, d;
    cin >> n >> m >> d;

    vector<int> x(n);
    iota(x.begin(), x.end(), 0);
    for (int i = 0, a; i < m; ++i) {
        cin >> a;
        swap(x[a - 1], x[a]);
    }
    vector<int> f(n);
    for (int i = 0; i < n; ++i) f[x[i]] = i;

    iota(x.begin(), x.end(), 0);
    for ( ; 0 < d; d >>= 1) {
        if (d & 1) multiple(x, f);
        multiple(f, f);
    }

    for (int i = 0; i < n; ++i)
        cout << x[i] + 1 << '\n';

    return 0;
}

解法2．巡回記法

$f$ を巡回記法で表す．巡回記法とは置換を互いに素な巡回置換の積で表したものである． $N$ を頂点集合として， $i \in N$ から $f(i)$ へ弧を張ることによって構成される有向グラフ $G_f$ とする．このとき， $f$ が置換であることから，各頂点の入次数と出次数はちょうど1である．すなわち， $G_f$ の各強連結成分は自己ループのみからなる1頂点か，有向閉路のいずれかである． $G_f$ の各有向閉路は $f$ の巡回記法のある巡回置換に対応する．
$f^d (i)$ は $G_f$ 上で頂点 $i$ から隣接する頂点へ移動することを $d$ 回繰返して到達できる頂点と一致する．したがって，各有向閉路 $(c_0, c_1, \ldots, c_{k-1})$ に対して， $f^d(c_i)$ の値は $c_{(i + d) \bmod k}$ となる．

計算時間： $O(n + m)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    int n, m, d;
    cin >> n >> m >> d;

    vector<int> x(n);
    iota(x.begin(), x.end(), 0);
    for (int i = 0, a; i < m; ++i) {
        cin >> a;
        swap(x[a - 1], x[a]);
    }
    vector<int> f(n);
    for (int i = 0; i < n; ++i) f[x[i]] = i;

    fill(x.begin(), x.end(), -1);
    for (int s = 0; s < n; ++s) {
        if (x[s] != -1) continue;
        vector<int> cycle = {s};
        for (int cur = f[s]; cur != s; cur = f[cur])
            cycle.push_back(cur);

        const int len = cycle.size();
        for (int i = 0; i < len; ++i)
            x[cycle[i]] = cycle[(i + d) % len];
    }

    for (int i = 0; i < n; ++i) cout << x[i] + 1 << '\n';

    return 0;
}

巡回記法は有向グラフを意識すると分かりやすくなった