CODE FESTIVAL 2017 Elimination Tournament-F Unicyclic Graph Counting の準線形解法

CODE FESTIVAL 2017 Elimination Tournament F-Unicyclic Graph Counting を時間計算量 $O(N\log^{2} N)$ で解く解法を紹介します。

問題リンク

atcoder.jp

問題概要

長さ $N$ の正整数列 $d$ が与えられる。頂点 $i$ の次数が $d_i$ であるような $N$ 頂点 $N$ 辺の単純連結グラフの個数を ${} \bmod {10^{9}+7}$ で求めよ。

$3 \le N$
$1 \le d_i \le N-1$
$\sum_i d_i = 2N$

定式化

まず、 $d_i=2$ となる頂点しか存在しない場合、解は $\frac{(N-1)!}{2}$ です。以下、 $d_i \neq 2$ を満たす頂点が存在するとします。

頂点の集合の中から、サイクルとして選択する頂点の集合を $S$ 、選択しない頂点の集合を $T$ とします。また、 $|S|=k, \sum_{v \in S} (d_v-2) = s$ とします。

ここで、 $3 \le k \le N-1$ とします。(前提より、この仮定を満たさない $k$ について、解は $0$ です)

また、いったん $2 \le \min_{v \in S} d_v$ 、 $1 \le s$ としておきます。

この時の解は(サイクルの作り方) $\times$ (サイクルを $1$ つの頂点としてみた時の木の数) $\times$ (サイクルから出る辺と頂点の対応付け) の形で書け、

$\displaystyle \frac{(k-1)!}{2} \times \frac{((N-k+1)-2)!}{\prod_{v \in T} (d_v-1)! \times (s-1)!} \times \frac{s!}{\prod_{v \in S} (d_v-2)!}$

と表せます。これを変形すると

$\displaystyle \frac{(N-k-1)!(k-1)!}{2 \times \prod_i (d_v-1)!} \times \prod_{v \in S} (d_v-1) \times s$

となります。この式では $\min_{v \in S} d_v=1$ や $s \le 0$ のケースが $0$ を返すので、さっきの $2$ つの仮定は取り除いて ok です。

ここで、 $t_i:=d_i-1$ とします。

すべての $0 \le k \le N$ について、 $\{1,2,\ldots,N\}$ の部分集合 $S\ (|S|=k)$ についての $\prod_{v \in S} t_v \times \sum_{v \in S} (t_v-1)$ が求まれば、解は高速に求まります。

ここで、いったん和の部分を無視したとき、 $k$ についての答えは $[ x^{k}] \prod_i (1+t_ix)$ と書けます。

和の部分が入るときのみ $t_i$ ではなく $t_i(t_i-1)$ をかけることを考えると、 $k$ についての答えは $\displaystyle[x^{k}] \sum_j \left((t_j(t_j-1)x) \times \prod_{i \neq j} (1+t_ix)\right)$ と書けます。

これを変形すると $\displaystyle[x^{k}]\prod_i (1+t_ix) \sum_j \frac{t_j(t_j-1)x}{1+t_jx}$ となります。 $\displaystyle f:=\prod_i (1+t_ix), g:=\sum_i \frac{t_i(t_i-1)x}{1+t_ix}$ とすると、 $k$ についての答えは $[x^{k}] f\times g$ と書けます。

ここで、 $f,g$ ともに次数が小さいものからマージするテクニックで $O(N\log^{2} N)$ で求めることができます。

よって、この問題を $O(N\log^{2} N)$ で解くことができました。