Network Reliability (700) AOJ-ICPC 2345 $O(N^2 2^N)$ 解
$ V = \left\{ 1, \ldots, N \right\} $ とする。 $ f(S) = (S \subset V \text{に誘導される部分グラフが連結な確率})$ とおく。
実は $ 1 \in S$ しか考えなくていいことがわかって、連結にならない確率を考えると、1 を含む連結成分で場合分けすればよい。 $ K(U, V)$ を $ U, V$ を結ぶ辺の数とすると、
$$ f(S) = 1 - \sum_{U \subset S, 1 \in U} f(U) p ^ {K\left(U, S - U\right)} $$ となる。
$ X(U)$ を $ U$ に含まれる辺の数とすると、 $ K(U, V) = X(U) + X(V) - X(U \cup V) $ と書けるので、先ほどの式は
$$ f(S) p ^ {-X(S)} = 1 - \sum_{U \subset S, 1 \in U} f(U) p ^ {-X(U)} p ^ {-X(S - U)} $$
と書ける。
\begin{align} F(S) = f(S) p ^ {-X(S)} (1 \in S) \\ G(S) = p ^ {-X(S)} (1 \notin S, S \neq \phi) \\ H(S) = 1 (1 \in S) \end{align}
とすると、
$$ H - F \ast G = F $$
と書けることが分かる $ \ast $ は subset convolution
$I(S)$ を $S = \phi$ のときのみ 1 となる subset convolution の単位元とすると、
$$ H - F \ast G = F \\ H = F \ast G + F \\ H = F \ast (G + I) $$
と変形できる。よって、 $F = H \ast \mathrm{inv}(G + I)$ と求まる。
(subset convolution の inv は zeta 後の各多項式を inv すればいいそうです、Nyaan さんに教えてもらいました。)
