非常好题目。
在一个大小为 \(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)} \] 标签：frac,Third,cdot,sum,nx,AGC032F,线段,mathrm From： https://www.cnblogs.com/SError0819/p/17700955.html