blogskol

思わず声に出して読みたくなるブログ

ARC163-D Sum of SCC

頂点番号が小さい方から大きい方へ向けられた辺を large edge と呼ぶことにする.
$g(t,n,m)$ : 頂点集合 $[n$ ], large edge が $m$ 本, 強連結成分が $t$ 個のトーナメントグラフの個数とする.
答えは $\sum_t t\times g(t,N,M)$ である.

まず $g(1,n,m)$ について考える.
頂点集合 $[n$ ], large edge が $m$ 本であるグラフの個数は $E=\binom{n}{2}$ として $\binom{E}{m}$ と表せる. 従って、

$\displaystyle g(1,n,m)=\binom{E}{m}-\sum_{t\geq 2} g(2,n,m)$

が成立する.

次に $g(t,n,m)$ から $g(t+1,*,*)$ への遷移を考える. トーナメントグラフの強連結成分はパスグラフであることに注意して、最後の強連結成分を追加することを考える.

$[n+n'$ ] を $A,B$ に分割する方法であって、

$\displaystyle |A|=n, |B|=n', | \{ (a,b) \in A\times B \mid a \lt b \} | = e$

を満たすものの個数を $v(n,n',e)$ とする
$v$ は頂点 $n+n'$ を $A,B$ のどちらに追加するかを考えることで $n+n'$ の昇順に求める事が出来る.

追加する強連結成分の頂点数と large edge をそれぞれ $n',m'$ とすると、以下の配る DP が考えられる.

$\displaystyle g(t+1,n+n',m+m'+e) += g(t,n,m) g(1,n',m')v(n,n',e)$

したがって $g(t,N,M)$ を求める事が出来る.
以上の漸化式は $t$ に依存していないことに注目すると $\sum_{n,n',m',e} g(1,n',m')v(n,n',e)$ を前計算しておくことが可能で、本番はこれで通した.