SRM 620 RandomGraph
题目大意：给你一个图无向图G，G有n个顶点，所有的边
这个题目还是比较有意思的。
首先我们可以把4个以上转化为不超过4个，也就是说变成求这个问题的一个互补问题，因为转化之后的问题情况就变得少了很多，从而能够更好的求解
接下来我们考虑怎么求图 G 中所有联通子图的顶点数都不超过4个的概率。首先不超过4个的情况只有如下几种
第一种情况就是只有一个点在子图中，第二种情况是有两个顶点在图中，第三种和第四种是有3个顶点在子图中。我们可以把一个图中 第一种情况的个数设为 a,第二种情况的个数设为 b, 第三种和第四种情况的个数设为 c, 那么我们要求的就是图中只有这四种情况的概率。我们设 f(r, a, b, c) 表示 r 个顶点中 a 个第一种情况，b 个第二种情况，c个第三和第四种情况的概率。那么我们要求的就是 f(n, a, b, c) 且 a + 2b + 3c == n 的概率（其中 n 是图 G 的顶点个数）。那么接下来就是怎么算 f(r, a, b, c) 的事情了。
我们假设现在有一个图 T，其中有 a 个第一种情况， b 个第二种情况， c 个第三和第四种情况。那么我们再加入一个顶点的时候，会发生什么呢？
- 我们加入的点单独成为一个子图，也就是说不和任何的点有边连接，变成 f(r+1, a+1, b, c), 那么这种情况的概率是 (1-p)^(a+2b+3c)
- 我们和第一种情况中的任何一个点有连接，那么就变成了 f(r+1, a-1, b+1, c), 这样情况的概率是 (ap)(1-p)^(a-1)*(1-p)^(2b+3c)，首先是从 a 个点中选择一个，然后算概率
- 我们和第一种情况种的任何两个点连接，变成一个第三种情况，那么就变成了 f(r+1, a-2, b, c+1), 概率为 (a(a-1))/2p^2 (1-p)^(a-2)(1-p)^(2b+3c)
- 我们和第二种情况种的某一个点连接，把连接的这个第二种情况变成第三种情况，也就是 f(r+1, a, b-1, c+1), 概率为 (1-p)^a (2b)p(1-p)^(2b-1) (1-p)^3c,其中标记出来的是从第二种情况种选择一个点进行连接，然后算的概率
- 我们和第二种情况种的两个点进行连接，从而变成第四种情况（注意这里和上面的区别），也就是 f(r+1, a, b-1, c+1), 概率为 (1-p)^a b p^2 (1-p)^(2b-2)(1-p)^3c.
接下来就可以用动态规划的思想来计算所有的 f(r, a, b, c) 了，然后计算出来之后我们求的所有 a+2b+3c == n 的 f(n, a, b, c)，记这个为 s 的话，那么我们最终要求的结果就是 1-s。到这里结束了
