相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3925
神犇题解Ⅰ：http://blog.csdn.net/skywalkert/article/details/47792065
神犇题解Ⅱ：http://www.cnblogs.com/yousiki/p/6437155.html
解题报告
题目上说：
对于$n$个$[0,1]$之间的随机变量$x_1,x_2,\cdots ,x_n$，第$k$小的那个的期望值是$\frac{k}{n+1}$
即加入$k$条边后恰好有生成树的情况的最大边的期望权值为$\frac{k}{n+1}$
设$g_k$为加入$k$条边后恰好使所有点连通的方案数
于是原题的答案为$\frac{1}{m+1}\sum\limits_{i=1}^{m}{\frac{i \cdot g_i}{m \choose i}}$
设$f_k$为加入$k$条边后原图不连通的方案数
我们可以交换一下求和顺序可使答案变为：$\frac{1}{m+1}\sum\limits_{i=0}^{m}{\frac{f_i}{m \choose i}}$
于是问题变为求$f_k$与$g_k$
我们首先可以发现，$f_k$加$g_k$一定等于所有的方案
那么设点集$S$的诱导子图中的边数为$cnt_{S}$，仅对于点集$S$有效的$f_k,g_k$为$f_{S,k},g_{S,k}$
则有：$f_{S,k}+g_{S,k}={cnt_S \choose k}$，于是只需要求出$g_{S,k},f_{S,k}$中的任意一个
类比带标号的连通图计数，我们可以列出递推式：$f_{S,i+j} = \sum\limits_{T \subset S}{g_{T,i} {cnt_{S-T} \choose j}}$
又$g_{S,k}={cnt_S \choose k} – f_{S,k}$，所以这个递推式可以直接递推
于是这题就做完啦！时间复杂度：$O(m 4^n)$
又因为上述$T \subset S$所以我们直接枚举子集，复杂度优化到$O(m 3^n)$
Thank you for the auspicious writeup. It in fact was a amusement account it. Look advanced to far added agreeable from you! However, how could we communicate?
898152 911391I believe other internet site proprietors need to take this website as an model, extremely clean and excellent user friendly style and style, as effectively as the content. Youre an expert in this subject! 140698
193739 402982I discovered your weblog site on google and check a few of your early posts. Continue to maintain up the quite good operate. I just additional up your RSS feed to my MSN News Reader. Seeking forward to reading much more from you later on! 3979
503610 940434I like this website because so significantly helpful material on here : D. 977914
686691 403150Ive been absent for a whilst, but now I remember why I used to love this site. Thank you, I will try and check back much more often. How often you update your web site? 235837
680714 185607Thrilled you desire sensible business online guidelines keep wearing starting tools suitable for the specific web-based business. cash 554726
518017 714615There is noticeably lots of funds to comprehend about this. I assume youve produced certain nice points in features also. 672186
493408 967745I real pleased to find this website on bing, just what I was seeking for : D too saved to bookmarks . 178437
937143 585678Some times its a pain inside the ass to read what weblog owners wrote but this internet web site is rattling user friendly ! . 798511
128706 257516This really is how to get your foot within the door. 84552
665991 709732I truly appreciated this gorgeous weblog. Make certain you maintain up the great function. Greatest Regards . 164711
7368 916534really nice post, i undoubtedly adore this exceptional website, carry on it 209511
Hello! This is my 1st comment here so I just wanted to give a quick shout out and tell you I genuinely enjoy reading through your articles. Can you suggest any other blogs/websites/forums that cover the same subjects? Appreciate it!