首先先证明几个引理。
- \(\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}\)，可以当作合法方案除以总方案来理解。
根据期望公式：
由于 \(\dfrac{d(1-nx)}{dx}=-n\)：
证毕。
- \(\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}\) 的结论再交换求和号即可得到答案。
朴素 \(O(n\log n)\) 计算即可。