ARC151 B - A < AP (500)
それぞれの地点で元の配列より辞書順で小さくなった時の場合の数を考える
ある地点で小さくなるというのは逆にその地点までは元と同じ値である
$ p_i = iの場合は必ず元と同じ値になるので小さくできない
事前に何個の集合があるかを持っておく
最初は$ n個
集合自体はUnionFindで管理
集合は同じ値にすべき物を管理する
それぞれの位置で以下を行う
$ p_i=iなら飛ばす
そうでなくて$ (i,p_i)が同じ集合になければそれらを繋げる
繋げた後集合の数を1減らす
その位置で小さくなる場合の場合の数を求める
今繋げたもの同士以外はどんな値を取っても良い
今繋げた集合間は片方が片方より小さいペアのいずれかなので$ \frac{m(m+1)}{2}パターン
集合の数を$ s とすると場合の数は$ \frac{m^s(m+1)}{2} 個
ここで集合の数を毎回求めると遅いので結合時に減らしている