以下の内容はhttps://noimi.hatenablog.com/entry/2021/12/02/183550より取得しました。

JOI 難易度 10 circuit - 電気回路の結線 (Circuit) 解説

問題概要 $\left( 0, \ldots, N - 1\right)$ の置換 $\sigma$ と正整数 $K$ が与えられる。置換 $\tau$ であって、 $\tau ^ K = \sigma$ を満たすものを一つ求めよ。

制約 - $N, K \le 10 ^ 5$

$N\sqrt{N}$ 解がこちらで説明されています。segtree.hatenablog.com

置換を有向グラフとして見るといくつかのサイクルに分解できることが知られている。置換 $\sigma$ が誘導する有向グラフを $G(\sigma)$ で表す。

$G(\sigma)$ において $x$ が属するサイクルの大きさを $C(\sigma, x)$ とおく。

性質 1 一番簡単な場合、 $G(\sigma)$ が一つのサイクルからなる場合を考える。( $C(\sigma, x) = N$ ) このとき、 $gcd(N, K) = 1$ が必要十分条件である。

prf

$\sigma(x) = x + 1 (\mod N)$ としても一般性を失わない。

十分性 $\mod N$ での $K$ の逆元を $inv(K)$ と書く。

$\tau(x)$ = $\tau(x) + inv(K) (\mod N)$ とすればよい。

必要性 $C(\tau ^ K, x) = \dfrac{C(\tau, x)}{\gcd(C(\tau, x), K)}$

より、 $C(\tau ^ K, x) \lt N$ がわかる。

性質 2 任意の $1 \le x \le N$ について、 $C(\sigma, x)$ = $C(\sigma, \tau(x))$ が成り立つ。

prf

$C(\tau ^ K, x) = \dfrac{C(\tau, x)}{\gcd(C(\tau, x), K)}$

と

$C(\tau, x) = C(\tau, \tau(x))$

を合わせることでわかる。

上の性質より、 $G(\tau)$ で同じサイクルに属する頂点は、 $G(\sigma)$ で属するサイクルのサイズが等しいことがわかる。これにより、頂点は $C(\sigma, x)$ が等しい頂点ごとに独立に考えることができる。

よって、 $\sigma$ はサイズ $L$ のサイクル $M$ 個からなるものとしてよい。

性質 3 $\gcd\left(\dfrac{K}{\gcd\left(K, M\right)}, L\right) = 1$ が必要十分条件である。

prf

$G(\sigma)$ のサイクルに $1, \ldots, M$ の番号をつける。

$\lambda$ : 置換に対し、 $id(\lambda, x)$ で $G(\lambda)$ において $x$ が属するサイクルの番号を表す。

$id(\tau, x)=id(\tau,\tau ^ K (x)) = id(\tau, \sigma (x))$ を複数回適用することで、

$id(\sigma, x) = id(\sigma, y) \Rightarrow id(\tau, x) = id(\tau, y)$ がわかる。

よって、ある正整数 $T$ が存在して、 $C(\tau, x) = TL$ と書ける。

今、この $x, T$ を固定する。

$\tau ^ {KL} (x) = x$ より、 $TL | KL \Leftrightarrow T|K$

また、 $\tau ^ {K} (x) = \sigma (x)$ と性質 1 より、 $gcd\left(K, T\right) = 1$ を満たす必要がある。

以上二つより $id(\sigma, \tau ^ T (x)) = id(\sigma, x)$

これは直感的にもわかりやすいです(L * T 個の長方形で、T 個進んだら元のグループに戻ってくるようにするしかない)。

相異なる $id(\sigma, x)$ に関する $T$ は総和が $M$ である。

これらを合わせて、主張を得る。

なので、アルゴリズムとしては

サイクルに分解する。
サイクルのサイズごとにまとめる
$gcd(K, M)$ を $T$ として、 $\sigma ^ T$ を $\sigma$ に取り換えてサイクルが一つの場合に帰着する。
性質 1 の証明のように構成する。

という流れで構成できます。計算量は $O(N)$ です。(gcd のパートはちょっと考えると消えることがわかります)

以上の内容はhttps://noimi.hatenablog.com/entry/2021/12/02/183550より取得しました。
このページはhttp://font.textar.tv/のウェブフォントを使用してます

不具合報告/要望等はこちらへお願いします。
モバイルやる夫Viewer Ver0.14