JOI2007 春合宿 - circuit

• 問題
• AC

置換の累乗根を考える問題。ひとまず置換を巡回置換に分解すると、巡回置換の長さと個数だけに意味があることがわかる。与えられた置換が長さ$l$の巡回置換$C(l)$個から構成されるとして、累乗根を探す。

一般に長さ$L$の巡回置換を$k$乗すると長さ$L/\gcd(L, k)$の巡回置換$\gcd(L, k)$個に分解される。逆に長さ$l$の巡回置換がいくつかある時、$L = \gcd(L, k)l$を満たすような$L$があれば、長さ$l$の巡回置換を$\gcd(L, k)$個合わせた置換の$k$乗根として長さ$L$の巡回置換を構成できる。

そこで、長さ$l$の巡回置換に対して可能な長さ$L$の集合を$S(l, k)$とする:

$$S(l, k) = \{L : L = l\gcd(L, k), \: L \le f(l)l\}$$

長さ$L \in S(l, k)$を採用するとき、長さ$l$の巡回置換を$\gcd(L, k)$個消費して（$k$乗根となる長さ$L$の）巡回置換が作れることになる。したがって、この問題は$S(l, k)$内の長さを重複を許して自由に使って$C(l)$個をちょうど消費する問題になる。（重複あり部分和問題） この問題をすべての$l$について解けばよい。解けない$l$があれば解なしとなる。

計算量について。$S(l, k)$を求めるのは$1, 2, ...f(l)l$をすべて試せばよくて、$f(l)l$の総和はちょうど$N$に等しいのでこの部分は${O}(N)$である。$L$は$k$の約数に$l$を掛けたものだから、$S(l, k)$のサイズは$k$の約数の総数$d(k)$を超えない。したがって、各部分和問題のサイズは$C(l)d(k)$で総和は$Nd(k)$。全体の計算量も${O}(Nd(k))$になる。