实数范围内随机 学习笔记
有一些题目很好玩，它的随机不是在有限整数范围内，而是在实数范围内随机，然后让你算什么什么的期望，而这个期望往往又是并不复杂的分数。
在线段上任取 \(n\) 点就是经典例子。
看起来很简单，但是一旦跟无穷相关，感觉不积分不太可做。
可惜，我并不会积分，去世！
现在，让我们来看一些经典结论：
- 在 \([0,1]\) 中随机选 \(n\) 个数，最小值期望为 \(\frac{1}{n+1}\)。
Proof(0)（极其感性理解，谨慎观看）
考虑对于某一个数，小于 \(x\) 概率为 \(x\)，那么 \(x=\frac{1}{n}\) 时候，\(n\times \frac{1}{n}=1\)，趋于平衡。
Proof(1)（不够严谨，但是毕竟绕开了积分）
考虑把从 \([0,1]\) 变成从 \([1,x]\) 中选取整数但是 \(x\) 极大。
然后枚举最小值大小和方案数来计算得
\[ans=\frac{\Sigma_{i=1}^{x}nx(x-i)^{n-1}}{x^n} \]考虑上面这个式子形如很多 \(k\) 次方和，有经典结论：
\(1\) 到 \(x\) 的 \(k\) 次方和为 \(k+1\) 次式，最高次系数为 \(\frac{1}{k+1}\)。
由于 \(x\) 足够大，所有非最高次项直接忽略，最后期望为 \(\frac{x}{n+1}\)
其实加粗这句话也已经是运用导函数结论干事情了……
Proof(2)
先把最小改为求最大，本质相同。
考虑设最大值为 \(x\)，那么根据期望公式，我们应该求出最大值为 \(x\) 的概率，得到了这个式子：
\[\int_{0}^{1} nx·x^{n-1} \]\[=n\int_{0}^{1} x^n \]\[=\frac{n}{n+1} \]终究逃不过积分的命运……
如果最小值，则部分 \(x\) 改为了 \((1-x)\)，需要简单换元，这里不赘述了。
- 中随机选 \(n\) 个数，第 \(k\) 小值期望为 \(\frac{k}{n+1}\)。
Proof(1)（感性理解，不保证严谨）
数学归纳法。
我们假设抠出最小值 \(x\)。
剩下的相当于在 \([x,1]\) 中随机选 \(n-1\) 个点，最小值期望。
然后这个式子是根据 \(x\) 线性相关的，而期望也是线性的，所以直接合并没有影响。
然后就可以求次小，第三小……发现答案就是上面的式子。
Proof(2)
见这里
但是我个人认为这个做法相当不严谨啊……
Proof(3)
还是暴力开开式子，然后分部积分，懒得写，咕咕咕。
2.1 推论：在长度为 \(1\) 的线段上随机选 \(n-1\) 点分为 \(n\) 段，则每段长度期望为 \(\frac{1}{n}\)。
有了上面的结论，这个较为显然。
有一段长为 \(l\) 的线段，有 \(n\) 个区间，左右端点在 \([0,l)\) 间均匀随机（可能不是整数），求被至少 \(k\) 段区间覆盖的长度的期望，对 \(998244353\) 取模，\(n,k\le 2000\)。
Solution：考虑 \(2n\) 个点将区间分成 \(2n+1\) 块，根据刚才结论每块期望长为 \(\frac{1}{2n+1}\)，那么分开计算每一块被 \(i\) 条区间覆盖的概率，如果 \(i\ge k\) 就加进答案中。
计算每一块被 \(i\) 条区间覆盖的概率，则是不复杂的组合数问题，DP 或者组合数计算都行了。
- 在长度为 \(1\) 的线段上随机选 \(n-1\) 点分为 \(n\) 段，则最小段长度期望为 \(\frac{1}{n^2}\)。
Proof
跟上面差不多，但是钦定了最小值之后每一项不小于它，那么有些项不太一样了，不过整体差不多的。
例题 2：P6130 随机红包
将长度为 \(1\) 的线段随机分成 \(n\) 段，求第 \(k\) 小的期望长度，\(n,k\le 10^7\)。
类似于上文，我们钦定最小，在剩下的里面找最小就是第二小了。
然后你推一下第二小发现是 \(\frac{1}{n}(\frac{1}{n}+\frac{1}{n-1})\)，再推会发现这玩意又可以数学归纳法，无敌了。
反正答案是
\[\frac{1}{n}\Sigma_{i=n-k+1}^{n}\frac{1}{i} \]暂时不知道了，后面补充。