题解 CF1187F【Expected Square Beauty】
whiteqwq
2021-09-04 16:51:10
[CF1187F Expected Square Beauty](https://www.luogu.com.cn/problem/CF1187F)解题报告：
[更好的阅读体验](https://www.cnblogs.com/xiaoziyao/p/15226690.html)
## 题意
定义一个序列 $x$ 的美丽值 $B(x)$ 为将 $x$ 划分成所有元素都相等的子段的最小子段数，对于位置 $i$，它的值在 $[l_i,r_i]$ 中随机，且是一个整数，求 $E(B(x)^2)$。
$1\leqslant n\leqslant 2\times 10^5,1\leqslant l_i\leqslant r_i\leqslant 10^9$。
## 分析
套路题，来水一个题解。
首先考虑 $E(B(x))$ 怎么求，实际上它就是 $E(\sum_{i=1}^{n-1}[x_i\ne x_{i+1}])$，根据期望的线性性将它拆开求就好了。
同样地，$E(B(x)^2)$ 可以套路地转化成 $E(\sum_{i=1}^{n-1}\sum_{j=1}^{n-1}[x_i\ne x_{i+1}][x_j\ne x_{j+1}])$，拆开后我们就只要求一对位置对同时满足条件的概率。
分类讨论：（下面为了方便，设 $R(i)=E([x_i\ne x_{i+1}])$。）
- $i=j$，仍然等于 $R(i)$。
- $|i-j|>1$，不难发现两个位置互不影响，直接 $R(i)R(j)$。
- $|i-j|=1$（设 $i=j+1$），考虑容斥一下，那么概率为 $1-E([x_{i-1}=x_i])-E([x_i=x_{i+1}])+E([x_{i-1}=x_i=x_{i+1}])$，后面这个东西可以类似 $R(i)$ 一样计算。
计算上述值非常简单，时间复杂度 $O(n\log mod)$。
这里简单提一下 $R(i)$ 的计算方式吧，我们可以求相等的概率，然后发现每个取值会取遍区间 $i$ 和区间 $i+1$ 的交，我们就直接将交的长度除以两个区间的长度之积就好了。
## 代码
为了方便，可以加入一个位置 $0$，其值在 $[0,0]$ 内随机。
```cpp
#include<stdio.h>
const int maxn=200005,mod=1000000007;
int n,ans,sum;
int l[maxn],r[maxn],R[maxn],len[maxn],invlen[maxn];
inline int min(int a,int b){
return a<b? a:b;
}
inline int max(int a,int b){
return a>b? a:b;
}
int ksm(int a,int b){
int res=1;
while(b){
if(b&1)
res=1ll*res*a%mod;
a=1ll*a*a%mod,b>>=1;
}
return res;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&l[i]);
for(int i=1;i<=n;i++)
scanf("%d",&r[i]);
l[0]=r[0]=0,invlen[0]=1;
for(int i=1;i<=n;i++){
len[i]=r[i]-l[i]+1,invlen[i]=ksm(len[i],mod-2);
R[i]=(1-1ll*max(0ll,min(r[i],r[i-1])-max(l[i],l[i-1])+1)*invlen[i]%mod*invlen[i-1]%mod+mod)%mod;
if(i>2)
sum=(sum+R[i-2])%mod;
ans=((ans+R[i])%mod+2ll*sum*R[i]%mod)%mod;
}
for(int i=1;i<n;i++){
int P=(1ll*(1-(1-R[i])-(1-R[i+1]))%mod+mod)%mod,ext=1ll*max(0ll,min(min(r[i-1],r[i+1]),r[i])-max(max(l[i-1],l[i+1]),l[i])+1)*invlen[i-1]%mod*invlen[i+1]%mod*invlen[i]%mod;
ans=(ans+2ll*(P+ext)%mod)%mod;
}
printf("%d\n",ans);
return 0;
}
```