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 のパートはちょっと考えると消えることがわかります)