気晴らしに難易度10を単体解きしようと思って考えた
頭を使わずに考察していると悪い表現になって、場合分けと境界処理が大変な解が出た
やる気が無かったので解説を探すが、どこにも無かった
頭を使って考察すると多少マシな解が出て、解説を自分で書くことにした
問題
各頂点の入次数、出次数ともに1の有向グラフを構築せよ。
ただし、頂点iのK個先の頂点がa[ i ]でなければならない。
1<=N,K<=10^5
解法
各頂点の入次数、出次数ともに1の有向グラフは、サイクルが何個かある形だ。
サイズSのサイクルでは、それぞれの頂点はK%S個進んだ所の頂点に対応する。
そして、gcd(S,K)個ずつの周期で自由に対応させることができる成分ができる。
具体的には、S/gcd(S,K)のサイズの成分が独立にgcd(S,K)個作れる。
与えられるiとa[i]の関係から、同じ成分に属する頂点集合がわかり、サイズのみが注目するべき情報である。
サイズSの成分をすべて作ることを考える。
前に求めた情報から、成分をまとめていくつ作れるかがわかっているので、復元付きのナップザックの処理をすることで、成分の作り方がひとつ求められる。（作れないときは0を出力して即終了する。）
求めた作り方に従って適切に辺を張り、答えとする。
（↑ココの正確さと詰める速さが大事）
ナップザックの重さがサイズ一種類につきO(√N)通りなので、計算量は全体でO(N√N)
前よりWAと混乱が減っていて、実装力が付いた感じがする
