首先先证明几个引理。
- \(\text{Lemma \#1}\)：
长度为 \(1\) 的线段上随机取 \(n-1\) 个点，将其分成 \(n\) 段，长度最短段的长度期望为 \(\dfrac{1}{n^2}\)。
证明：
我不知道能不能 \(\text{Min-Max}\) 容斥，但有更简单的做法。
假设最小段长度为 \(l_{\min}\)，考虑枚举 \(x\)，计算 \(x\le l_{\min}\) 的概率。
由于要求最小值 \(\ge x\)，所以可以先将所有区间长度减去 \(x\)，剩下的长度为 \(1-nx\)，由于取出 \(n-1\) 个点，所以 \(P(l_{\min}\ge x)=(1-nx)^{n-1}\)，可以当作合法方案除以总方案来理解。
根据期望公式：
\[\begin{aligned}\mathbb E(l_{\min})&=\int_0^{\frac{1}{n}}P(l_{\min}\ge x)dx\\&=\int _{0}^{\frac{1}{n}}(1-nx)^{n-1}dx\end{aligned} \]由于 \(\dfrac{d(1-nx)}{dx}=-n\)：
\[\begin{aligned}\mathbb E(l_{\min})&=\int _{0}^{\frac{1}{n}}(1-nx)^{n-1}dx\\&=-\frac{1}{n}\int_0^{\frac{1}{n}}(1-nx)^{n-1}d(1-nx)\\&=\frac{1}{n^2}\end{aligned} \]证毕。
- \(\text{Lemma \#2}\)：
长度为 \(1\) 的线段上随机取 \(n-1\) 个点，将其分成 \(n\) 段，长度第 \(k\) 短段的长度期望为 \(\dfrac{1}{n}\sum\limits_{i=1}^k\dfrac{1}{n-i+1}\)。
手算发现 \(\mathbb E(l_{\min_2})=\mathbb E(l_{\min})+\dfrac{1-n\mathbb E(l_{\min})}{(n-1)^2}=\dfrac{1}{n^2}+\dfrac{1}{n(n-1)}\)，就是先减去最小值的长度，再在剩余的长度里面取最小值。
同理，\(\mathbb E(l_{\min_3})=\mathbb E(l_{\min_2})+\dfrac{1-n\mathbb E(l_{\text{min}})-(n-1)\left(\mathbb E(l_{\text{min}_2})-\mathbb E(l_{\min})\right)}{(n-2)^2}=\dfrac{1}{n^2}+\dfrac{1}{n(n-1)}+\dfrac{1}{n(n-2)}\)。
归纳可证。
知道了这个你就可以把随机红包切了。
- \(\text{Solution}\)
我们可以把披萨旋转一下，使得第一刀位于水平线上。（假如披萨是立着放的。）于是我们只需要考虑剩下 \(n-1\) 刀。
然后我们把平面分成 \(3\) 个区域，每个区域都是 \(\dfrac{2\pi}{3}\) 的角度。考虑一个转换：
在一个长度为 \(\dfrac{1}{3}\) 的线段中，随机撒 \(n-1\) 个 \(3\) 颜色随机的点，求两端颜色不同的段的长度的期望。
相当于把所有半径映射到一个扇形中。
我们钦定前 \(k-1\) 短的段两端颜色相同，第 \(k\) 短的段符合我们的条件。容斥一下，这个概率为 \(\dfrac{1}{3^{k-1}}-\dfrac{1}{3^k}\)，然后带入 \(\text{Lemma \#2}\) 的结论再交换求和号即可得到答案。
\[\begin{aligned}\text{ans}&=\frac{1}{3}\sum\limits_{k=1}^n\left(\frac{1}{3^{k-1}}-\frac{1}{3^k}\right)\frac{1}{n}\sum\limits_{i=1}^k\frac{1}{n-i+1}\\&=\frac{1}{n}\sum\limits_{i=1}^n\frac{1}{3^i(n-i+1)}\end{aligned} \]朴素 \(O(n\log n)\) 计算即可。
标签：mathbb,frac,Third,min,dfrac,text,长度,AGC032F From： https://www.cnblogs.com/Ender32k/p/17569086.html