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を追加していけばいい。
yukicoder #484: 収穫
解説の理解
yukicoder #483: マッチ並べ
各座標を頂点としてグラフを書く。連結成分ごとに考えてみる。
グラフが木になる場合は、根付き木と見なして親から子へ、マッチの頭薬を向けて並べていけばいい。
グラフが閉路を1個だけもつ場合。まず、その1個の閉路を、片方向（時計回り、反時計回りどちらでも)にならべていく。そうしたら、先の方法と同様に、サイクルを根付き木の根と見なして残りのマッチを並べていけばいい。
グラフが閉路を2個以上もつ場合はこれらの埋め方は不可。
閉路が2個以上あるかどうかの判定は次数の合計を見ればいい。
次数/2 = 頂点数-1
のときは木
次数/2 = 頂点数
のときは閉路1個
次数/2 > 頂点数
のときは閉路2個以上
yukicoder #482: あなたの名は
解法
N>=2なので
ソートするのにかかる最小の交換回数をsとしたとき
s-K>=0 かつ 2 | (s-K) ならばOK
与えられているのは順列で、グラフにしてみるとsの求め方はわかりやすい。複数のサイクルに分割できてサイクルごとにソートするのが最も交換回数が少なくて済む。
yukicoder #250: atetubouのzetubou
実行時間をf(X,D)とすると
f(X,D) = (X+D-1)!/(X!(D-1)!)
これを普通に計算するとオーバーフローなどが面倒。
なのでとりあえず素因数分解した形で、肩の足し引きだけしておく。
素因数を１個ずつ掛けていって、tを超えないか、オーバーフローしないかをチェックする。
