CF1187F Expected Square Beauty(期望)

题目

做法

\(B(x)=\sum\limits_{i=1}^n I_i(x),I_i(x)=\begin{cases}1&x_i≠x_{i-1}\\0&x_i=x_{i-1}\end{cases}\)

\(E(B(x)^2)=E(\sum\limits_{i=1}^n I_i(x)\sum\limits_{j=1}^n I_j(x))=E(\sum\limits_{i=1}^n\sum\limits_{j=1}^n I_i(x)I_j(x))=\sum\limits_{i=1}^n\sum\limits_{j=1}^n E(I_i(x)I_j(x))\)

分类讨论一下\(E(I_i(x)I_j(x))\)

\(|i-j|>1\)，这两个互不影响，则\(E(I_i(x)I_j(x))=E(l_i(x))E(l_j(x))\)
\(i=j\)，因为\(l(x)\)函数仅为\(1\)和\(0\)，故\(E(I_i(x)I_j(x))=E(l_i(x))\)
\(|i-j|=1\)详细讨论一下：

\(q_i=P(x_{i-1}=x_i)=E(x_{i-1}=x_i)=max(0,\frac{min(r_{i-1},r_i)-max(l_{i-1},l_i)}{(r_{i-1}-l_{i-1})(r_i-l_i)})\)

\(E(I_i(x))=1-q_i\)

则\(E(I_i(x)I_{i+1}(x))=E(x_{i-1}≠x_i\And x_i≠x_{i+1})\)

故等于\(1-q_i-q_{i+1}+E(x_{i-1}=x_i\And x_i=x_{i+1})\)

其中\(E(x_{i-1}=x_i\And x_i=x_{i+1})=\frac{min(r_{i-1},r_i,r_{i+1})-max(l_{i-1},l_i,l_{i+1})}{(r_{i-1}-l_{i-1})(r_i-l_i)(r_{i+1}-l_{i+1})})\)

可以用\(O(n)\)算出来

Code

#include<bits/stdc++.h>

typedef int LL;

const LL maxn=1e6+9,mod=1e9+7;

inline LL Read(){

	LL x(0),f(1); char c=getchar();

	while(c<'0' || c>'9'){

		if(c=='-') f=-1; c=getchar();

	}

	while(c>='0' && c<='9'){

		x=(x<<3ll)+(x<<1ll)+c-'0'; c=getchar();

	}return x*f;

}

LL n,ans,sum;

LL l[maxn],r[maxn],q[maxn],E[maxn];

inline LL Pow(LL base,LL b){

	LL ret(1);

	while(b){

		if(b&1) ret=1ll*ret*base%mod; base=1ll*base*base%mod; b>>=1;

	}return ret;

}

inline LL P(LL x,LL y,LL z){

	LL L(std::max(l[x],std::max(l[y],l[z]))),R(std::min(r[x],std::min(r[y],r[z])));

	return std::max(0ll,1ll*(R-L)*Pow(1ll*(r[x]-l[x])*(r[y]-l[y])%mod*(r[z]-l[z])%mod,mod-2)%mod);

}

inline LL Calc(LL x){

	LL y(x+1),ret(0);

	if(x>1) ret=P(x-1,x,y);

	return ((1ll-1ll*(q[x]+q[y])%mod+mod)%mod+ret)%mod;

}

int main(){

	n=Read();

	for(LL i=1;i<=n;++i){

		l[i]=Read();

	}

	for(LL i=1;i<=n;++i){

		r[i]=Read()+1;

		LL R(std::min(r[i],r[i-1])),L(std::max(l[i],l[i-1]));

		q[i]=std::max(0ll,1ll*(R-L)*Pow(1ll*(r[i-1]-l[i-1])*(r[i]-l[i])%mod,mod-2)%mod);

		E[i]=1ll*(1-q[i]+mod)%mod;

		sum=1ll*(sum+E[i])%mod;

	}

	for(LL i=1;i<=n;++i){

		LL tmp(sum);

		for(LL j=std::max(1,i-1);j<=std::min(n,i+1);++j)

		    tmp=1ll*(tmp-E[j]+mod)%mod;

		ans=1ll*(ans+1ll*E[i]*tmp%mod)%mod;

		if(i>1) ans=1ll*(ans+Calc(i-1))%mod;

		if(i<n) ans=1ll*(ans+Calc(i))%mod;

		ans=1ll*(ans+E[i])%mod;

	}

	printf("%d\n",ans);

	return 0;

}

巴特西

CF1187F Expected Square Beauty(期望)

题目

做法

Code

最新文章

热门文章