yukicoder No.1392 Don't be together
順列 に対し,
と
の間に辺を張ったグラフは, どの連結成分も閉路になることが知られてまふ. 連結成分ごとに, 閉路をたどるような順番で次のdpを更新しまふ.
:
番目の頂点まで調べてグループ数がちょうど
個, そして
番目の頂点が現在の連結成分で最初に調べた頂点と違うグループなら
, 同じなら
閉路の最初の頂点を見るときには必ず で, サイクル内最後の頂点においては必ず
ということに気を付ければあとはうまく更新できると思いまふ.
なお, 対称性より, 頂点の更新順は閉路のサイズの組合わせさえあっていれば という順番で更新されるものとして良いれふ.
