no_imi https://blog.hatena.ne.jp/no_imi/ のいみのいみのいみのいみ https://noimi.hatenablog.com/ onlinejudge.u-aizu.ac.jp $ 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)} $$… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fnoimi.hatenablog.com%2Fentry%2F2022%2F07%2F10%2F004354" title="Network Reliability (700) AOJ-ICPC 2345 $O(N^2 2^N)$ 解 - のいみのいみのいみのいみ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2022-07-10 00:43:54 rich https://noimi.hatenablog.com/entry/2022/07/10/004354 1.0 100%