[AGC032F] One Third-526互联

非常好题目。

在一个大小为 \(1\) 的圆上选出 \(n\) 条半径将其分为 \(n\) 块，记每块的面积为 \(S_1,S_2,\dots,S_n\)，求

\[\min_{i=1}^{n}\{|S_i-\frac{1}{3}|\} \]

的期望值。答案对 \(10^9+7\) 取模。

\(2\le n\le 10^6\).

考虑以一个点的半径为 x 轴，将圆分为三块大小为 \(\frac{2\pi}{3}\) 的扇形，往上面撒 \(n-1\) 个点，令三个扇形中的点的颜色分别为 RGB，把所有线段的夹角对 \(\frac{2\pi}{3}\) 取模，即

在 \([0,\frac{2\pi}{3})\) 随机取 \(n-1\) 个点，将每个点染为 RGB，两端颜色不同的线段长度的最小值的期望。

枚举第 \(k\) 小的线段，那么颜色的限制就是 \(\displaystyle\frac{1}{3^{k-1}}-\frac{1}{3^k}\).

再记 \(E(k)\) 为在长为 \(1\) 的线段上划分出 \(n\) 段，第 \(k\) 短的线段的期望长度。

即求

\[\frac{1}{3}\sum_{i=1}^{n}(\frac{1}{3^{i-1}}-\frac{1}{3^i})\cdot E(i) \]

接下来考虑 \(E\) 的求解。

这个东西可以去看 P6130 随机红包。

先考虑求第 \(1\) 短的线段的期望长度。

记最小值为 \(x\)，不妨让 \(n\) 条线段一起减去 \(x\)，然后在长为 \(1-nx\) 的线段上任取 \(n-1\) 个点，即

\[E(1)=\int_{0}^{\frac{1}{n}}(1-nx)^{n-1}\mathrm{d}x \]

由于 \(\displaystyle\frac{\mathrm{d}(1-nx)}{\mathrm{d}x}=-n\)：

\[=-\frac{1}{n}\int_{0}^{\frac{1}{n}}(1-nx)^{n-1}\mathrm{d}(1-nx) \]

\[=-\frac{1}{n^2}\cdot(1-nx)^{n-1}\Big|_{0}^{\frac{1}{n}} \]

\[=\frac{1}{n^2} \]

减去 \(n\) 个 \(E(1)\)，那么剩余总长度为 \(\frac{n-1}{n}\).

求解 \(E(2)\).

\[E(2)=E(1)+\frac{n-1}{n}\cdot\int_{0}^{\frac{1}{n-1}}(1-(n-1)x)^{n-2}\mathrm{d}x \]

\[=E(1)+\frac{n-1}{n}\cdot\frac{1}{(n-1)^2} \]

\[=\frac{1}{n^2}+\frac{1}{n(n-1)} \]

以此类推得到 \(E\) 数组：

\[E(k)=\frac{1}{n}\cdot\sum_{i=1}^{k}\frac{1}{n-i+1} \]

回到最终答案。

\[\frac{1}{3}\sum_{i=1}^{n}(\frac{1}{3^{i-1}}-\frac{1}{3^k})\cdot\frac{1}{n}\cdot\sum_{j=1}^{i}\frac{1}{n-j+1} \]

\[\frac{3}{n}\sum_{j=1}^{n}\frac{1}{n-j+1}\sum_{i=j}^{n}(\frac{1}{3^{i-1}}-\frac{1}{3^i}) \]

然后你发现有个 \(\frac{1}{3^n}\) 消不掉。但是枚举段数的时候，\(n\) 处的概率不能这样计算，应用 \(1\) 减去 \(1\sim n-1\) 的所有值。也就是说其实不必考虑这一项。

答案即

\[\frac{1}{n}\cdot\sum_{j=1}^{n}\frac{1}{3^j(n-j+1)} \]