AGC008-E Next or Nextnext
問題概要
サイズNの数列Aが与えられる。サイズNの1~Nの順列であるPの中で、
p[i]=a[i],p[p[i]=a[i]の少なくとも一方を満たすPの数を数える。
メモ
途中まではAtCoderの公式解説と同じ考察をする、「ただの閉路」の数え上げがDPで行える理由が分からなかったので(分かる人いたら誰か教えてください)、組み合わせで殴りたくなる。
サイズが3以上の奇数である閉路の数え上げ
閉路のサイズをS、そのような閉路の数がK個、その中からM個のペアを作る場合の数は
となる。(2つの閉路を選んだ時のペアの作り方はS通りあるし、ある1つの閉路の使い方は2通りある。)
Mが1変わったときの差分は高速に求められるので、十分高速に全ての場合を計算できる。
それ以外の閉路の数え上げ
閉路のサイズをS、そのような閉路の数がK個、その中からM個のペアを作る場合の数は
となる。(2つの閉路を選んだ時のペアの作り方はS通りある。)
Mが1変わったときの差分は高速に求められるので、十分高速に全ての場合を計算できる。
閉路のサイズごとにこれらを求め、掛け合わせると答えが出てうれしいです。
ACの提出を載せます。