CodeForces【期望】1187F-Expected Square Beauty_综合

CodeForces 1187F-Expected Square Beauty

◆题目传送门◇

题目大意

给定一个序列 $x$ ，定义函数 $B (x)$ 为将 $x$ 划分为一些子区间，使得这些区间中所有元素都相等的区间数量。对于 $x$ 中的第 $i$ 个元素，其取值范围为 $l_i,r_i]$ ，求 $E(B^2(x))$ ，答案要求化简为 $PQ\frac{P}{Q}$ 后求出 $P?Q?1mod  109+7P\cdot Q^{-1}\mod 10^9+7$ 的值。

分析

直接求 $B (x)$ 似乎不太方便。我们尝试定义一个新函数 $T_i(x)$ ，当 $x_i=x_{i-1}$ 时，函数值为 $0$ ，反之为 $1$ 。特别的，当 $i = 1$ 时， $T_i(x)=1$ 。

易得： $B(x)=∑i=1nTi(x)B(x)=\sum_{i=1}^{n}T_i(x)$ 。

那么： $B2(x)=[∑i=1nTi(x)]2=∑i=1n∑j=1nTi(x)Tj(x)B^2(x)=[\sum_{i=1}^{n}T_i(x)]^2\\ =\sum_{i=1}^{n}\sum_{j=1}^{n}T_i(x)T_j(x)$

所以： $E(B2(x))=E(∑i=1n∑j=1nTi(x)Tj(x))=∑i=1n∑j=1nE(Ti(x)Tj(x))E(B^2(x))=E(\sum_{i=1}^{n}\sum_{j=1}^{n}T_i(x)T_j(x))\\=\sum_{i=1}^{n}\sum_{j=1}^{n}E(T_i(x)T_j(x))$

我们记 $T_i(x)=1$ 的概率为 $p_i$ 。接下来我们分三种情况讨论：

当 $∣ j ? i ∣ > 1$ 时，此时 $T_i(x)$ 与 $T_j(x)$ 是独立的，此时 $E(T_i(x)T_j(x))=p_ip_j$ 。

当 $i = j$ 时， $T_i(x)$ 与 $T_j(x)$ 是相同的事件，此时 $E(T_i(x)T_j(x))=p_i$ 。

当 $∣ j ? i ∣ = 1$ 时， $T_i(x)$ 与 $T_j(x)$ 不是独立事件，我们必须另求此时概率：

我们假设 $i = j + 1$ 。

我们先求有两个相邻元素相等的概率：

当 $x_{i-1}=x_i$ 时，总共有 $min\{r_i,r_{i-1}\}-\max\{l_i,l_{i-1}\})(r_{i+1}-l_{i+1}+1)$ 情况，此时概率为 $(min?{ri,ri?1}?max?{li,li?1})(ri+1?li+1+1)(ri?1?li?1+1)(ri?li+1)(ri+1?li+1+1)\frac{(\min\{r_i,r_{i-1}\}-\max\{l_i,l_{i-1}\})(r_{i+1}-l_{i+1}+1)}{(r_{i-1}-l_{i-1}+1)(r_i-l_i+1)(r_{i+1}-l_{i+1}+1)}$

同理可得 $x_i=x_{i+1}$ 的概率为 $(min?{ri,ri+1}?max?{li,li+1})(ri?1?li?1+1)(ri?1?li?1+1)(ri?li+1)(ri+1?li+1+1)\frac{(\min\{r_i,r_{i+1}\}-\max\{l_i,l_{i+1}\})(r_{i-1}-l_{i-1}+1)}{(r_{i-1}-l_{i-1}+1)(r_i-l_i+1)(r_{i+1}-l_{i+1}+1)}$

但由于两个事件不是独立的，我们需要减掉它们的交集即三个元素相等的概率： $min?{ri?1,ri,ri+1}?max?{li?1,li,li+1}+1(ri?1?li?1+1)(ri?li+1)(ri+1?li+1+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)}$

所以： $E(Ti(x)Tj(y))=1?(min?{ri,ri?1}?max?{li,li?1})(ri+1?li+1+1)(ri?1?li?1+1)(ri?li+1)(ri+1?li+1+1)?(min?{ri,ri+1}?max?{li,li+1})(ri?1?li?1+1)(ri?1?li?1+1)(ri?li+1)(ri+1?li+1+1)+min?{ri?1,ri,ri+1}?max?{li?1,li,li+1}+1(ri?1?li?1+1)(ri?li+1)(ri+1?li+1+1)E(T_i(x)T_j(y))=1-\frac{(\min\{r_i,r_{i-1}\}-\max\{l_i,l_{i-1}\})(r_{i+1}-l_{i+1}+1)}{(r_{i-1}-l_{i-1}+1)(r_i-l_i+1)(r_{i+1}-l_{i+1}+1)}\\-\frac{(\min\{r_i,r_{i+1}\}-\max\{l_i,l_{i+1}\})(r_{i-1}-l_{i-1}+1)}{(r_{i-1}-l_{i-1}+1)(r_i-l_i+1)(r_{i+1}-l_{i+1}+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)}$

综上所述，所以： $E(B2(x))=∑i=1n∑j=1nE(Ti(x)Tj(x))=∑i=1n(pi+pi∑∣j?i∣>1pj+E(Ti?1(x)Ti(x)))E(B^2(x))=\sum_{i=1}^{n}\sum_{j=1}^{n}E(T_i(x)T_j(x))\\=\sum_{i=1}^{n}(p_i+p_i\sum_{|j-i|>1}p_j+E(T_{i-1}(x)T_i(x)))$

注意由于我们最后答案要求用到分数，所以我们必须手写一个分数类来完成。

这个分数类里面，无论是加减乘除都可以直接模。

时间复杂度为 $O (n)$ 。

参考代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;typedef long long ll;
const int Maxn=2e5;
const ll Mod=1e9+7;inline ll QuickPow(ll a,ll k) {
    ll ret=1;while(k) {
    if(k&1)ret=(ret*a)%Mod;a=(a*a)%Mod;k>>=1;}return ret;
}int N;
ll L[Maxn+5],R[Maxn+5];
struct Frac {
    ll x,y;ll real_num() {
    return (x%Mod*QuickPow(y,Mod-2)%Mod+Mod)%Mod;}Frac operator + (const Frac &rhs) const {
    Frac ret;ret.x=(this->x*rhs.y%Mod+this->y*rhs.x%Mod)%Mod;ret.y=(this->y*rhs.y)%Mod;return ret;}Frac operator - (const Frac &rhs) const {
    Frac ret;ret.x=(this->x*rhs.y%Mod-this->y*rhs.x%Mod+Mod)%Mod;ret.y=(this->y*rhs.y)%Mod;return ret;}Frac operator * (const Frac &rhs) const {
    Frac ret;ret.x=(this->x*rhs.x)%Mod;ret.y=(this->y*rhs.y)%Mod;return ret;}
};
Frac P[Maxn+5];Frac Calc(int i) {
    int nxt=i+1;ll t1=max(0LL,min(R[i],R[nxt])-max(L[i],L[nxt])+1);ll t2=max(0LL,min(R[i-1],R[i])-max(L[i-1],L[i])+1);ll t3=max(0LL,min(R[i-1],R[nxt])-max(L[i-1],L[nxt])+1);ll s1=t2*(R[nxt]-L[nxt]+1)%Mod;ll s2=t1*(R[i-1]-L[i-1]+1)%Mod;ll s3=min(t1,min(t2,t3));Frac ret;ret.y=(((R[i]-L[i]+1)*(R[nxt]-L[nxt]+1))%Mod)*(R[i-1]-L[i-1]+1)%Mod;ret.x=(ret.y-(s1+s2-s3))%Mod;return ret;
}int main() {
    #ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifscanf("%d",&N);for(int i=1;i<=N;i++)scanf("%lld",&L[i]);for(int i=1;i<=N;i++)scanf("%lld",&R[i]);P[1].x=1,P[1].y=1;for(int i=2;i<=N;i++) {
    ll cnt=max(0LL,min(R[i],R[i-1])-max(L[i],L[i-1])+1);P[i].x=((R[i]-L[i]+1)*(R[i-1]-L[i-1]+1)-cnt)%Mod;P[i].y=(R[i]-L[i]+1)*(R[i-1]-L[i-1]+1)%Mod;}Frac sum;sum.x=0,sum.y=1;for(int i=1;i<=N;i++)sum=sum+P[i];Frac ans;ans.x=0,ans.y=1;for(int i=1;i<=N;i++) {
    Frac now=sum;for(int j=max(1,i-1);j<=min(N,i+1);j++)now=now-P[j];ans=ans+(now*P[i]);if(i>1)ans=ans+Calc(i-1);ans=ans+P[i];if(i+1<=N)ans=ans+Calc(i);}printf("%lld\n",ans.real_num());return 0;
}