olpheの競プロ帖

競プロ問やアルゴリズム等の考察します

2019-02-18から1日間の記事一覧

AGC008-E Next or Nextnext

問題概要 サイズNの数列Aが与えられる。サイズNの1~Nの順列であるPの中で、 p[i]=a[i],p[p[i]=a[i]の少なくとも一方を満たすPの数を数える。 メモ 途中まではAtCoderの公式解説と同じ考察をする、「ただの閉路」の数え上げがDPで行える理由が分からなかった…