Codeforces #397 D: Artsem and Saunders

まず2式

g(h(x)) = x

h(g(x)) = f(x)

を別々に考えてみる。

g(h(x)) = x

を満たすg,hは

例えば

g(x)=x

h(x)=x

があり、必ず構成できる。

また

h(g(x)) = f(x)

については

g(x) = x, h(x) = f(x)

とすればよく、これもf(x)の値によらない。

ところが、2式を同時に条件とすると成り立たない場合がある。（入力例2)

なので2式を使って解が存在する条件を求める。(関数fだけで表す)

f(f(x)) = f(x)

これで解があるか調べられる。

解の構成を考える。

g(f(x))

= g(h(g(x))

= １(g(x))

= g(x)

g(f(x)) = g(x)

h(g(x)) = f(x)

の2式より解を作っていく。

g(f(x)) = g(x)

より

y = f(x)

とすると

g(y) = g(x)

これによりmを決める。(素集合を考えればいい)

z=g(x) として1<=z<=m

g(f(x)) = z

h(z) = f(x)

なのでf(x)の値ごとにzを追加していけばいい。