【AGC032F】One Third（概率）（积分）

传送门

---

题解：

首先第一步转化，每一刀顺时针120度逆时针120度再切一刀。

落在以第一刀为 $0$度， $[0,\frac{\pi}{3})$里面染成红色，落在 $[\frac{\pi}{3},\frac{2\pi}{3})$为绿色，落在 $[\frac{2\pi}{3},\pi)$染成蓝色。

把所有刀模 $\frac{\pi}{3}$扔到第一个区间，现在相当于一条长 $\frac{1}{3}$的线段 $0$处为红色， $\frac{1}{3}$为蓝色，中间还有 $n-1$个点，位置和颜色均匀随机，所有相邻点把线段分成了一共 $n$段，询问最短的两端颜色不同的线段长度的期望。

把所有线段拿出来排序，考虑答案为第 $i$短的线段，意味着前 $i-1$的线段两端颜色相同，概率为 $\frac{1}{3^{i-1}}\cdot \frac{2}{3}$。

现在问题就只剩下，第 $k$短的线段的期望长度是多少。

这个好像是一个经典问题，和随机的第 $k$大有点类似但完全不同。

现在考虑初始线段长度为 $1$的情况

首先考虑最短的线段 $L_{min}$。

我们希望计算 $E(L_{min})$，一个通用做法是计算 $P(L_{min}\geq x)$也就是概率分布函数，然后对 $P$积分。

考虑计算 $P(L_{min}\geq x)$，最短的为 $x$，那么我们每段预留出 $x$，直接把 $nx$切掉扔了，剩下 $n$段 $n-1$个分隔符必须留在 $1-nx$里面，则：

$P(L_{min}\geq x)=(1-nx)^{n-1}$

积分得到：

$\begin{aligned} E(L_{min})&=\int_{0}^\frac{1}{n}P(L_{min}\geq x)\mathrm{d}x\\ &=\int_{0}^{\frac{1}{n}}(1-nx)^{n-1}\mathrm{d}x\\ &=\frac{1}{n}\int_{0}^1x^{n-1}\mathrm{d}x\\ &=\frac{1}{n^2} \end{aligned}$

考虑次小值，把最小值丢掉之后，次小值就是剩下线段的最小值，再把最小值接回去：

$E(L_{submin})=\frac{1-E(L_{min})}{(n-1)^2}+E(L_{min})=\frac{1}{n}(\frac{1}{n}+\frac{1}{n-1})$

同理 $k$小值的表达式为 $E(L_{kthmin})=\frac{1}{n}\sum\limits_{i=0}^{k-1}\frac{1}{n-i}$

则答案就是 $\sum\limits_{i=1}^{n}\frac{2}{3^i}E(L_{ith\text{ }min})$。

化简一下就是 $\sum\limits_{i=1}^n\frac{1}{3^in(n-i+1)}$

---

代码：

#include<bits/stdc++.h>
#define ll long long
#define re register
#define cs const

cs int mod=1e9+7;
inline int add(int a,int b){a+=b-mod;return a+(a>>31&mod);}
inline int mul(int a,int b){ll r=(ll)a*b;return r>=mod?r%mod:r;}
cs int N=1e6+7;

int inv[N],inv3=(mod+1)/3;

int n,ans;
signed main(){
	scanf("%d",&n);inv[0]=inv[1]=1;
	for(int re i=2;i<=n;++i)inv[i]=mul(mod-mod/i,inv[mod%i]);
	int coef=inv[n];
	for(int re i=0;i<n;++i){
		coef=mul(coef,inv3);
		ans=add(ans,mul(coef,inv[n-i]));
	}
	std::cout<<ans<<"\n";
	return 0;
}

转载：https://blog.csdn.net/zxyoi_dreamer/article/details/102054689