[Educational Codeforces Round 67]F.Expected Square Beauty(平方期望)

[Educational——手把手教你如何计数系列·第一期]

题面

原题面

Let $x$ be an array of integers $x=[x_1,x_2,\dots ,x_n]$. Let’s define $B(x)$ as a minimal size of a partition of $x$ into subsegments such that all elements in each subsegment are equal. For example, $B([3,3,6,1,6,6,6])=4$ using next partition:$[3,3|6|1|6,6,6]$.
Now you don’t have any exact values of $x$, but you know that $x_i$ can be any integer value from $[l_i,r_i](l_i\le r_i)$ uniformly at random. All $x_i$ are independent.
Calculate expected value of $(B(x){)}^2$, or $E((B(x){)}^2)$. It’s guaranteed that the expected value can be represented as rational fraction $\frac{P}{Q}$ where $(P,Q)=1$, so print the value $P?Q^{?1}\mathrm{m}\mathrm{o}\mathrm{d}10^9+7$.

Input

The first line contains the single integer $n$ ($1\le n\le 2?10^5$) — the size of the array $x$.
The second line contains $n$ integers $l_1,l_2,\dots ,l_n$($1\le l_i\le 10^9$).
The third line contains $n$ integers $r_1,r_2,\dots ,r_n$ ($l_i\le r_i\le 10^9$).

Output

Print the single integer — $E((B(x){)}^2)$ as $P?Q^{?1}\mathrm{m}\mathrm{o}\mathrm{d}10^9+7$.

翻译

有一个长度为$n$的数列{xi}\{x_i\}{ xi?}，定义$B(x)$为将$x$划分为所有元素都相等的子段的最小子段数。对于$1\le i\le n$，$x_i$将等概率为$[l_i,r_i]$中的一个整数。给定$l_i,r_i$，求$(B(x){)}^2$的期望，即$E((B(x){)}^2)$，对$10^9+7$取模。
来自:洛谷

题解

神奇的期望题。
设事件$I(i)$为$i$,$i?1$两个数相同这一个事件的发生或者不发生。
容易发现$B(x)={\sum }_{i=1}^{n}I(i)$,其中$I(1)$默认是一定发生的。
注意这里的$B(x),I(i)$都是事件。
然后同时平方$(B(x){)}^2=({\sum }_{i=1}^{n}I(i){)}^2$
由期望性质得:$E((B(x){)}^2)=E(({\sum }_{i=1}^{n}I(i){)}^2)$。
现在，我们就转化为求$E(({\sum }_{i=1}^{n}I(i){)}^2)$了。
接下来展开一下$E(({\sum }_{i=1}^{n}I(i){)}^2)=E({\sum }_{i=1}^n{\sum }_{j=1}^{n}I(i)I(j))$
注意这里乘法的意思是两个事件同时发生。
首先显然有$I(i)I(i)=I(i)$，然后我们可以将两个无关的事件直接分开，显然对于$I(i),I(j)(|i?j|>1)$两个事件是无关的，因此我们可以把式子分为:
$E({\sum }_{i=1}^n{\sum }_{j=1}^{n}I(i)I(j))=E({\sum }_{i=1}^n(I(i)+I(i){\sum }_{|i?j|>1}I(j)+I(i?1)I(i)+I(i)I(i+1)))={\sum }_{i=1}^n(E(I(i))+E(I(i)){\sum }_{|i?j|>1}E(I(j))+E(I(i?1)I(i))+E(I(i)I(i+1)))$
现在考虑计算$E(I(i))$。(注意接下来的等号都仅仅是数值上的相等)
由于这是一个0/1事件那么就有$E(I(i))=P(I(i))$也就是分别在$[l_{i?1},r_{i?1}],[l_i,r_i]$随意取一个数不相等的概率，显然就是$1?\frac{min(r_{i?1},r_i)?max(l_{i?1},l_i)+1}{(r_{i?1}?l_{i?1}+1)(r_i?l_i+1)}$,首先满足两区间相交，记为$p_i$。
然后是$E(I(i)I(i+1))$,同理有$E(I(i)I(i+1))=P(I(i)I(i+1))$,可以认为是在$[l_{i?1},r_{i?1}],[l_i,r_i],[l_{i+1},r_{i+1}]$随意取一个数都相等的概率,为$\frac{min(r_{i?1},r_i,r_{i+1})?max(l_{i?1},l_i,l_{i+1})+1}{(r_{i?1}?l_{i?1}+1)(r_i?l_i+1)(r_{i+1}?l_{i+1}+1)}$,然后互不相同的就容斥一下变为$1?p_{i+1}?p_i+\frac{min(r_{i?1},r_i,r_{i+1})?max(l_{i?1},l_i,l_{i+1})+1}{(r_{i?1}?l_{i?1}+1)(r_i?l_i+1)(r_{i+1}?l_{i+1}+1)}$(满足三区间相交)，记为$val(i)$。
那么就有$E((B(x){)}^2)={\sum }_{i=1}^n(p_i+p_i?{\sum }_{|i?j|>1}{p}_j+val(i?1)+val(i))$。
依次计算即可。注意各种各样奇怪的细节。
复杂度:$O(n\log \mathrm{m}\mathrm{o}\mathrm{d})$

实现

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
using namespace std;
#define MAXN 200000
#define MOD 1000000007
#define LL long long
int n,l[MAXN+5],r[MAXN+5];
int p[MAXN+5],q[MAXN+5],sum;
LL add(LL a,LL b){
    return (a+b)%MOD;}
LL mul(LL a,LL b){
    return 1LL*a*b%MOD;}
LL dec(LL a,LL b){
    return (a-b+MOD)%MOD;}
int fst_pow(int a,int b){
    int res=1;while(b){
    if(b&1)res=mul(res,a);a=mul(a,a);b>>=1;}return res;
}
int val(int i){
    int ans=1;ans=dec(ans,p[i]),ans=dec(ans,p[i+1]);int L=max(l[i-1],max(l[i],l[i+1])),R=min(r[i-1],min(r[i],r[i+1]));if(L<R)ans=add(ans,mul(R-L,fst_pow(mul(mul(r[i]-l[i],r[i-1]-l[i-1]),r[i+1]-l[i+1]),MOD-2)));return ans;
}
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]);r[i]++;}int sum=0;for(int i=1;i<=n;i++){
    int L=max(l[i],l[i-1]),R=min(r[i],r[i-1]);if(L<R)p[i]=mul(R-L,fst_pow(mul(r[i]-l[i],r[i-1]-l[i-1]),MOD-2));q[i]=dec(1,p[i]);sum=add(sum,q[i]);}//i==1 默认值int ans=0;for(int i=1;i<=n;i++){
    ans=add(ans,q[i]);int ps=dec(sum,q[i]);if(i>2)ans=add(ans,val(i-1)),ps=dec(ps,q[i-1]);if(i<n)ans=add(ans,val(i)),ps=dec(ps,q[i+1]);ans=add(ans,mul(q[i],ps));//printf("%d\n",ans);}printf("%d",ans);
}