Educational Codeforces Round 4 - E. Square Root of Permutation
解説
functionalグラフでかつ、と
はpermutationなので、
と
は
となる有向グラフを考えた時、シンプルなサイクルになることがわかる。
となる
を考えよう。
このとき、、
となる
が必要なことがわかる
が偶数のとき
とすればよい
が奇数のとき
となる
の巡回サイクルとは別の
をみつける(これがないときは作れないことが証明できる)
,
として作ることができる
となり、以上で必要性を満たさないときは必ずつくれる
