競技プログラミング 知識集積所

ARC228 D - Amidakuji 2

あみだくじ2

問題ページ解答例

考え方

数学の言葉で書いてあるが、タイトルにあるようにあみだくじの問題。
つまり、同じあみだくじをコピペで大量連結して、指定のあみだくじを全部作りたい。
素材にすべきあみだくじを求めてください、ということ。

まず、答えが出た前提で、本当に条件を満たしているか確認するチェッカーを作る。
つまり、あみだくじ $A$ を何個かつなげることで $B$ にできるか判定するプログラムを書く。
これを行っておくことで、「この候補で無理なら不可能」というのを作る戦略が使えるようになる。

が、このチェッカー作成だけでもかなり難しいので、まずはそちらから解説する。
前提知識となる巡回表示についての話から。

巡回表示

あみだくじ（置換）は、巡回表示にした方が考えやすいことも多い。
例えば、あみだくじの行き先が $(4,1,5,2,3,6)$ と与えられた場合。
意味は、$1$ からは $4$ へ行く、$2$ からは $1$ へ行く、といったものである。
それを $(1,4,2),(3,5),(6)$ と書き直す。
意味は、$1,4,2$ が $4,2,1$ と順繰りに $1$ つずつズレる関係になっている、といったものである。

この形だと、同じあみだくじの $k$ 個連結が、巡回を $k$ 個ずらす話で済む。
よって、$A$ を $B$ にすることができるかの判断もしやすくなる。

実装は、単純である。
各数について、「まだ巡回の中に書いてなければ、あみだくじ $1$ 個ごとにどこへ行くか辿る」だけ。

チェッカー作成

あみだくじ $A$ を何個かつなげることで $B$ にできるか判定するプログラムを書く。

まず、$A$ の巡回表示を $1$ つ見る。
例えばそれが $(1,4,2)$ だったとしよう。
$B$ の方で、$1$ の行先、$4$ の行先、$2$ の行先、を見て同じように数を並べる。
これが $(1,3,2)$ のように中身の構成が異なれば、この時点で不可能であると判定される。
$(4,1,2)$ のように中身を順繰りにずらしても一致しない場合も不可能であると判定される。
これは、$B$ 側の先頭の数が $A$ 側のどこにあるか見て、実際に動かして判定するとよい。
その移動距離が次の処理にそのまま使える。

巡回で作れる場合、あみだくじを何連結するかの値の制約ができる。
例えば、長さ $3$ の巡回が距離 $1$ ずらして一致する場合、連結数を $3$ で割った余りは必ず $1$ である。

これを全ての巡回について行い、矛盾する制約が $1$ つもなければ、それを満たす値が連結数となる。
これは中国剰余定理でどうとでもなる……ように見えて、C++ではそうもいかない。
中国剰余定理では、$\bmod$ の法がそれぞれの最小公倍数になる。
$N$ の値が最大 $500$ だと、入力次第ではこの最小公倍数が long long 型ですら余裕でオーバーフローする。
そのため、ここの処理も工夫しなくてはならない。

例えば「$12$ で割った余りが $3$」という制約があったとする。
これは「$4$ で割った余りが $3$」かつ「$3$ で割った余りが $0$」と素数の累乗ごとに分割できる。
これが元々あった「$2$ で割った余りが $1$」と矛盾しないかは、前者だけ調べればよく、それは簡単。

ということで、巡回の長さを素因数分解して、条件を素因数別にもつことでこの問題は解消できる。
矛盾が発生したら不可能であると判定される。

ここまでの処理を一度も不可能判定にならないように完遂できれば、$A$ を何連結かして $B$ にできる。
以上で、チェッカー作成ができた。

チェッカーを $1$ 回走らせる計算量は $O(N\log N)$ である。

$M=2$ である場合

チェッカーができたので、正しい保証がある解を作る必要がない。
「もしこれが解になっていないなら何をやっても無理」という候補を作れればよい。
作った後で、それをチェッカーにかければ、解である証明も不可能証明もできる。

まず、任意のあみだくじは、同じものを何連結かすると「結局全員元の位置に戻る」もの $E$ になる。
初めてそうなる連結数を「位数」と言い、巡回表示にしたときの各巡回の長さの最小公倍数で求められる。
（それで「結局全員元の位置に戻る」あみだくじ $E$ になることは、巡回の意味を考えれば明らかである）
例えば、巡回が $(1,4,2),(3,5),(6)$ であれば、位数は $\operatorname{lcm}(3,2,1) = 6$ である。
$6$ 連結すると、$1$ は $1,4,2,1,4,2,1$ という順に変化して元に戻るし、他も同様。

さて、与えられる順列が $P_1$ と $P_2$ の $2$ つである場合を考える。
そして、それらが仮に両方とも、あるあみだくじ $Q$ の何連結かで作れるとしよう。
つまり、$P_1 = Q^{e_1},P_2 = Q^{e_2}$ となっているとしよう。
すると、$P_1$ と $P_2$ は明らかに順序の入れ替えが可能である。

このとき、$e_1$ と $e_2$ は互いに素であると仮定してよい。
そうでない場合には、それらの最大公約数だけ $Q$ を連結したものを改めて $Q$ と定義すればよい。
そして、$P_1$ の位数が $k_1$、$P_2$ の位数が $k_2$、$Q$ の位数が $k_Q$ であるとしよう。

以下、しばらくこれらの数の性質を考察する。
【$k,e$ などについての考察ここから】

この場合、$P_1^{k_1} = Q^{k_1 e_1} = E$ となる。
ということは、$k_1 e_1$ が $k_Q$ の倍数になっているはずである。
これは、あみだくじ $k_1 e_1$ 連結を上から $k_Q$ 個ずつに区切ってみればわかる。
$k_Q$ 個ずつでそれぞれ $E$ になっているので、端数が出るとそれも $E$ になる。
これは、 $k_Q$ の最少性に矛盾している。

さらに、$k_1$ の最少性から、$e_1$ に $k_1$ 未満のどんな正整数をかけても $k_Q$ の倍数にならない。
ということは、構成素因数を考えれば、$k_1$ は $k_Q$ の約数でなければならない。
具体的には、$k_1 = k_Q/\gcd(k_Q,e_1)$ である。

これらは、$e_2$ と $k_2$ についても同じ関係が成り立つ。

すると、$\operatorname{lcm}(k_1,k_2)=k_Q$ となる。
これは、$\gcd(e_1,e_2)=1$ であることから成り立つ。
$k_Q$ の任意の素因数について、$k_1$ か $k_2$ のいずれかが $k_Q$ と同じ指数を持っているからである。

さて、ここで以下のように $k_1$ と $k_2$ を $k_1 = c_1k'_1, k_2 = c_2k'_2$ と積に分解する。

例えば、$k_1=120,k_2=90$ である場合、$k_Q=360$ で $c_1=15,k'_1=8,c_2=2,k'_2=45$ である。
また、その構成法から、これら $4$ つの間に以下が成り立つ。

さらに、$c_1e_1+c_2e_2$ と $k_Q$ が互いに素であることを示す。

$k_Q$ の素因数を $1$ つ選び、それを $p$ とする。
$k'_1$ と $k'_2$ のいずれかのみが $p$ を素因数にもち、その指数は $k_Q$ での指数と同じである。
$k'_1$ が $p$ を持っている側だとして一般性を失わない。
このとき、$c_1$ は $k'_1$ と互いに素なので、$p$ を素因数に持たない。
また、$k_1 = k_Q/\gcd(k_Q,e_1) = \operatorname{lcm}(k_Q,e_1)/e_1$ であることから、$e_1$ も $p$ を素因数に持たない。

一方、$c_2 e_2$ の積は素因数に $p$ をもつ。
$P'_2 = P_2^{c_2} = Q^{c_2e_2}$ の位数が $k'_2$ なので、$c_2e_2k'_2$ は $k_Q$ の倍数。
しかし、$k'_2$ は素因数 $p$ を持たないのだから、$c_2 e_2$ の積は素因数に $p$ をもつ。

とすると、$c_1e_1+c_2e_2$ は、$p$ の倍数とそうでない数の和なので、$p$ を素因数に持たない。
これは $k_Q$ の任意の素因数について言えるので、$c_1e_1+c_2e_2$ と $k_Q$ は互いに素である。

【$k,e$ などについての考察ここまで】

さて、$P'_1 = P_1^{c_1},P'_2 = P_2^{c_2}$ とすると、位数はそれぞれ $k'_1,k'_2$ となる。
$P'_1$ と $P'_2$ ももちろん順序の入れ替えが可能である。

そして、 $P'_1$ と $P'_2$ を連結したあみだくじ $P_0 = P'_1 P'_2$ のことを考える。
$c_1e_1+c_2e_2$ と $k_Q$ は互いに素であるので、拡張ユークリッドの互除法が適用できる。
つまり、$x(c_1e_1+c_2e_2)\equiv1\pmod{k_Q}$ となる正整数 $x$ が存在する。
この $x$ を用いると、$P_0^x = Q^{(c_1e_1+c_2e_2)x} = Q$ となる。
したがって、 $P_0^{e_1x} = Q^{e_1} = P_1,P_0^{e_2x} = Q^{e_2} = P_2$ となる。
よって、この $P_0$ は $Q$ と同じ条件を満たす、つまりその累乗で $P_1$ と $P_2$ が再現できる。

つまり、何らかの $Q$ が存在するなら、このようにして作った $P_0$ も必ず $Q$ としての条件を満たす。
言い換えれば、このようにして作った $P_0$ が $Q$ としての条件を満たさないなら、$Q$ は存在しない。
これにより、最初に述べた「もしこれが解になっていないなら何をやっても無理」という候補が作れた。

以上より、以下で解ける。

ただし、各 $k$ や $k'$、$c$ は巨大になる可能性がある。
そのため、チェッカー同様に素因数分解状態で管理すること。

計算量は $O(N\log N)$。

$M\geq 3$ である場合

順列の中から $2$ つを選んで、上述の方法で作った $P_0$ に置き換える。
これを $1$ 回やるごとに順列が $1$ つずつ減っていく。
最終的に $1$ つになったときの順列が答え。

毎回位数を求めなくても、置き換え時に位数も記録しておけば使いまわしがきく。

また、毎回チェッカーにかけなくても、全部合体してから $1$ 度だけチェッカーにかければ十分である。

計算量は $O(MN\log N)$。

$M=1$ である場合

これは、与えられたものをそのまま答えればよい。
特別処理しなくても、複数ある場合のコードにそのまま投げてよい。

全体の計算量

$M=1,2$ の場合も含めて $M\geq 3$ 用のコードに投げるとして、計算量は $O(\sum MN\log N)$ である。
$\sum MN \leq 250000$ で $N\leq 500$ であるため、間に合う。

入力例1での動作

$6$ 個のテストケースのうち、解がある $1$ ケース目と、解がない $2$ ケース目を追う。

まず、$1$ ケース目の入力を受け取る。

n: 3
m: 2
p1: {2, 3, 1}
p2: {3, 1, 2}

$P_1=(2,3,1)$ と $P_2=(3,1,2)$ はどちらも長さ $3$ の巡回 $1$ 個からなり、位数はどちらも $3$ である。

最初は恒等置換を候補とする。
$P_1$ を追加すると、そのまま候補は $P_1$ になる。

次に $P_2$ を追加する。
現在の候補と $P_2$ はともに位数が $3$ なので、位数に含まれる素因数 $3$ の成分を片方から消す。
現在の候補を $3$ 乗すると恒等置換になる。
それと $P_2$ を連結し、新しい候補は $P_0=P_2=(3,1,2)$ となる。

最後にチェッカーにかける。

まず $P_1$ を確認する。
候補 $P_0=(3,1,2)$ の巡回表示は $(1,3,2)$ である。
この巡回に並んでいる $1,3,2$ が $P_1$ でどこへ行くかを見ると、$(2,1,3)$ となる。
これは $(1,3,2)$ を $2$ 個ずらしたものである。
よって、この巡回から「連結数を $3$ で割った余りが $2$」という条件が得られる。
ほかに巡回はないので矛盾はなく、$P_1$ は $P_0$ の累乗で作れる。

次に $P_2$ を確認する。
同じく $1,3,2$ が $P_2$ でどこへ行くかを見ると、$(3,2,1)$ となる。
これは $(1,3,2)$ を $1$ 個ずらしたものである。
よって、「連結数を $3$ で割った余りが $1$」という条件が得られる。
こちらも矛盾はないので、$P_2$ も $P_0$ の累乗で作れる。

実際、$P_0^1=P_2$、$P_0^2=P_1$ である。
したがって、この候補は条件を満たす。

次に、$2$ ケース目の入力を受け取る。

n: 3
m: 2
p1: {2, 3, 1}
p2: {1, 3, 2}

$P_1=(2,3,1)$ の位数は $3$、$P_2=(1,3,2)$ の位数は $2$ であり、既に互いに素である。
そのため、特に累乗せずそのまま連結し、$P_0=P_1P_2=(3,2,1)$ を候補とする。

最後にチェッカーにかける。

候補 $P_0=(3,2,1)$ の巡回表示は $(1,3),(2)$ である。
この $1$ つめの巡回に並んでいる $1,3$ が $P_1$ でどこへ行くかを見ると、$(2,1)$ となる。
しかし、$(1,3)$ をどれだけ順繰りにずらしても $(2,1)$ にはならない。
つまり、候補の同じ巡回の中だけで移動するはずの頂点 $1$ が、$P_1$ では頂点 $2$ へ移動している。

この時点で $P_1$ は $P_0$ の累乗では作れないと判定できる。
よってチェッカーで不可能と判定され、このケースの答えは -1 となる。

注意点

特になし。

別解

特になし。