olpheの競プロ帖

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

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個のペアを作る場合の数は

\frac{K! \times S^M \times 2^{K-2M}}{M! \times 2^M \times (K-2M)!}

となる。(2つの閉路を選んだ時のペアの作り方はS通りあるし、ある1つの閉路の使い方は2通りある。)

Mが1変わったときの差分は高速に求められるので、十分高速に全ての場合を計算できる。

 

それ以外の閉路の数え上げ

閉路のサイズをS、そのような閉路の数がK個、その中からM個のペアを作る場合の数は

\frac{K! \times S^M}{M! \times 2^M \times (K-2M)!}

となる。(2つの閉路を選んだ時のペアの作り方はS通りある。)

Mが1変わったときの差分は高速に求められるので、十分高速に全ての場合を計算できる。

 

閉路のサイズごとにこれらを求め、掛け合わせると答えが出てうれしいです。

ACの提出を載せます。

atcoder.jp