以下是ChesterKing神仙的题解：
这题是真的神仙题……整整花了我两个礼拜来理解这题
首先这题据我了解有三种做法：纯OI做法、积分+数学推导、直接积分
请做好一定的心理准备，接下来的东西可能有点难理解（好像不是一点点的难吧……）
1.纯OI做法
首先我们根据期望的线性性，可以得到\(ans=\sum_{x=0}^mw(x)\times p(x)\)，其中\(w(x)\)为最大边为\(x\)时的对答案的贡献，\(p(x)\)为最大边为\(x\)时的概率。
由题目所给信息“对于\(n\)个之\([0,1]\)间的随机变量\(x1,x2,...,xn\)，第\(k\)小的那个的期望值是\(\frac{k}{n+1}\)”可知：\(w(x)=\frac{x}{m+1}\)。
\(\therefore ans=\sum_{x=0}^m\frac{x}{m+1}\times p(x)\)
设\(f(x)\)为最大边权的排名\(\ge x\)的概率，则\(p(x)=f(x-1)-f(x)\)。
\[ \therefore ans=\frac{1}{m+1}\times[f(0)-f(1)]+\frac{2}{m+1}\times[f(1)-f(2)]+...+\frac{m}{m+1}\times[f(m-1)-f(m)]+\frac{m+1}{m+1}\times[f(m)-f(m+1)] \]
\(\because f(0)=1,f(m+1)=0\) \[ \therefore ans=\frac{1}{m+1}\sum_{x=0}^mf(x) \] 定义\(f[S][i]\)为点集为\(S\)，选取了\(i\)条边使得点集不连通的方案数；同理，定义\(g[S][i]\)为点集为\(S\)，选取了\(i\)条边使得点集连通的方案数。
易得\(f[S][i]+g[S][i]={i\choose cnt[s]}\)，其中\(cnt[S]\)为点集\(S\)内的边数。
可以通过固定某定点\(P\)来进行转移，以达到不重复、不遗漏的计数。 \[ f[S][i+j]=\sum_{P \in S,T \subset S}g[T][i]\times{j \choose cnt[S-T]} \] 那么最终答案即为\(ans=\frac{1}{m+1}\sum_{x=0}^m\frac{f[all][x]}{x \choose cnt[all]}\)。
附上AC代码：
1 |
|
接下来的两种做法可能需要一定的高等数学知识，至于定积分、求导之类的运算法则，出门左拐度娘处。
讲接下来的两种做法之前，我们先来证明一个对于我个人很难理解的东西，因为接下来的做法都要用到。
求证：\(ans=\int_0^1f(x){\rm d}x\)，其中\(f(x)\)为答案\(>x\)的概率。
证明：设\(p(x)\)为答案\(=x\)的概率
易得：\(p(x)=\lim_{\Delta x \rightarrow 0}\frac{f(x)-f(x+\Delta x)}{\Delta x}=-f'(x)\)
根据期望的定义，得：\(ans=\int_0^1x\times p(x){\rm d}x\)
\[ \begin{align} \therefore ans&=\int_0^1x\times (-f'(x)){\rm d}x\\ &=\int_0^1x{\rm d}(-f(x))\\ &=[x\times (-f(x))]_0^1+\int_0^1f(x){\rm d}x \end{align} \] \(\because f(x)\)为答案\(>x\)的概率\(\qquad\therefore f(0)=1,f(1)=0\qquad\therefore ans=\int_0^1f(x){\rm d}x\)
证毕。
2.积分+数学推导
我们设一个函数\(P_S(t)\)表示当\(S\)[\(S\)为一个点集在原图中的导出子图]中的最大边为\(t\)时，\(S\)不连通的概率为\(P_S(t)\)。
那么有\(E(X)=\int_0^1P_{SIE}(t){\rm d}t\qquad\)[\(SIE\)为全集]\(\qquad\)(根据上面的证明可得)
我们可以方便地写出\(P(t)\)的递归式。
我们考虑一张图\(S\)，我们把其分成两部分(\(S_0\)与\(S-S_0\))，那么\(S_0\)连通而\(S\)不连通的概率为： \[ [1-P_{S_0}(t)]\times(1-t)^{E(S_0,S)} \] 其中\(E(S_0,S)\)为\(S_0\)到\(S- S0\)的边数。 \[ \begin{align} \therefore P_S(t)&=\sum_{S_0\not\subseteq S}(1-t)^{E(S_0,S)}\times [1-P_{S_0}(t)]\qquad[1\in S_0]\\ \therefore E(X)&=\int_0^1P_{SIE}(t){\rm d}t\\ &=\int_0^1\sum(1-t)^{E(S_0,S)}\times[1-P_{S_0}(t)]]{\rm d}t\qquad[1\in S_0)]\\ &=\sum\int_0^1(1-t)^{E(S_0,S)}{\rm d}t-\int_0^1(1-t)^{E(S_0,S)}\times P_{S_0}(t){\rm d}t\\ &=\sum\frac{1}{E(S_0,S)+1}-\int_0^1(1-t)^{E(S_0,S)}\times P_{S_0}(t){\rm d}t \end{align} \]
我们递归定义\(f[S_0][E(S_0,S)]=\int_0^1(1-t)^{E(S_0,S)}\times P_{S_0}(t){\rm d}t\)
\(\therefore f[1][k]=0,k\in[0,m]\qquad f[S][k]=\sum\frac{1}{k+E(S_0,S)+1}-f[S_0][k+E(S_0,S)]\)
然后直接暴力即可。
附上AC代码：
1 |
|
3.直接积分
首先记\(F(x)\)为答案\(>x\)的概率，可知\(ans=\int_0^1F(x){\rm d}x\)
\(F(x)\)等价于边权\(<x\)时不能使图连通的概率。有点难求，正难则反，考虑使图连通的概率。
记\(f(S)\)为集合\(S\)连通的概率，\(f(S)=1-\sum_{S'\subset S}f(S')\times(1-x)^{cnt}\)，其中\(cnt\)为\(S'\)和\(S-S'\)的边数。
可以发现，\(f(S)\)为关于\(x\)的多项式，可以做定积分。
也可以换一种理解的方式。
设\(f(x)\)为\(x==ans\)的概率密度函数，令\(F(x)=\int f(x){\rm d}x\) \[ \begin{align} ans&=\int_0^1xf(x){\rm d}x\\ &=\int_0^1x{\rm d}(F(x))\\ &=[x\times F(x)]_0^1-\int_0^1F(x){\rm d}x\\ &=1-\int_0^1F(x){\rm d}x\\ &=\int_0^1(1-F(x)){\rm d}x \end{align} \] \(F(x)\)的意义为取值\(\le x\)的概率，等价于每条边有\(x\)的概率出现，问图的连通概率。
注意：这种做法不知为何有点卡精度，需要开__float128。
1 |
|
后记：讲真，这的确是一道神题，很有思考的价值。
还有一小部分没有弄懂，就是“对于\(n\)个之\([0,1]\)间的随机变量\(x1,x2,...,xn\)，第\(k\)小的那个的期望值是\(\frac{k}{n+1}\)”的证明，最近还在思考，挖坑待填。
连续性变量的期望用微积分的方法来做会简便很多。
希望我写的博客能够帮助各位巨佬解这道题，另外我不觉得信息学和微积分有何冲突，只要是能做题的方法都是好方法，并没有哪种方法好一些，不应该有偏见，能掌握做题的方法肯定是越多越好。
就这样吧。
