CF1187F Expected Square Beauty解题报告：
题意
定义一个序列 (x) 的美丽值 (B(x)) 为将 (x) 划分成所有元素都相等的子段的最小子段数，对于位置 (i)，它的值在 ([l_i,r_i]) 中随机，且是一个整数，求 (E(B(x)^2))。
(1leqslant nleqslant 2 imes 10^5,1leqslant l_ileqslant r_ileqslant 10^9)。
分析
套路题，来水一个题解。
首先考虑 (E(B(x))) 怎么求，实际上它就是 (E(sum_{i=1}^{n-1}[x_i e x_{i+1}]))，根据期望的线性性将它拆开求就好了。
同样地，(E(B(x)^2)) 可以套路地转化成 (E(sum_{i=1}^{n-1}sum_{j=1}^{n-1}[x_i e x_{i+1}][x_j e x_{j+1}]))，拆开后我们就只要求一对位置对同时满足条件的概率。
分类讨论：（下面为了方便，设 (R(i)=E([x_i e 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(nlog mod))。
这里简单提一下 (R(i)) 的计算方式吧，我们可以求相等的概率，然后发现每个取值会取遍区间 (i) 和区间 (i+1) 的交，我们就直接将交的长度除以两个区间的长度之积就好了。
代码
为了方便，可以加入一个位置 (0)，其值在 ([0,0]) 内随机。
#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
",ans);
return 0;
}