SOJ#47. 序列期望mean 题解

description：

有 $n$n个随机变量 $x_1,x_2,...,x_n$x1​,x2​,...,xn​。给定 $l_1,...,l_n$l1​,...,ln​和 $r_1,...,r_n$r1​,...,rn​，变量 $x_i$xi​的值会等概率成为 $l_i,l_i+1,l_i+2,..,r_i$li​,li​+1,li​+2,..,ri​其中一个。

显然这 $n$n个随机变量的值会有一共 ${\prod }_{i=1}^n(r_i-l_i+1)$∏i=1n​(ri​−li​+1)种情况，且每种情况出现的概率为 ${\prod }_{i=1}^n\frac{1}{r_i-l_i+1}$∏i=1n​ri​−li​+11​。

对于某种情况，令 $h=\max \{x_1,x_2,...,x_n\}$h=max{x1​,x2​,...,xn​}，定义这种情况的权值为： ${\prod }_{i=1}^n(h-x_i+1)$∏i=1n​(h−xi​+1).

请问权值的 期望(即平均数) 是多少？请将答案对 $10^9+7$109+7取模后输出。

$30\%$30%： $n\le 5$n≤5， $r_i\le 10$ri​≤10。

$70\%$70%： $n\le 100$n≤100， $r_i\le 1000$ri​≤1000。

$100\%$100%： $n\le 1000$n≤1000， $r_i\le 10000$ri​≤10000。

solution：

• $30\%n\le 5,r_i\le 10$30%n≤5,ri​≤10

直接暴力搜索， $O\left(r^n\right)$O(rn)

• $70\%$70%： $n\le 100$n≤100， $r_i\le 1000$ri​≤1000

$O\left(r\right)$O(r)枚举最大值 $h$h是多少，计算其的贡献

$O\left(n\right)$O(n)枚举哪个x_i是h，要求 li​<=h<=ri​

再 $O\left(n\right)$O(n)计算其余每个数的贡献，为等差数列

• $100\%$100%： $n\le 1000$n≤1000， $r_i\le 10000$ri​≤10000

$O\left(r\right)$O(r)枚举最大值h是多少，计算其的贡献

用Dp代替上一种⽅法

$F\left[i\right]\left[0\right]$F[i][0] 表示前i个数中没有变量量等于h的等差数列列乘积之和；

$F\left[i\right]\left[1\right]$F[i][1]表示有变量量等于h的等差数列列乘积之和

$F\left[i\right]\left[0\right]=F[i-1]\left[0\right]\ast calc(i,h-1)$F[i][0]=F[i−1][0]∗calc(i,h−1)

$F\left[i\right]\left[1\right]=F[i-1]\left[1\right]\ast calc(i,h)$F[i][1]=F[i−1][1]∗calc(i,h)

If : li​<=h<=ri​,F[i][1]+=F[i][0]

其中calc代表计算第i个变量，最大值为h时的那个等差数列的和

等差数列：比如说h=5，l=1 r=3，贡献是 5,4,3 就是等差数列

code:

#include<cstdio>
#include<algorithm>
using namespace std;
#define p 1000000007
struct ben
{
	int x,y;
}a[100005];
int f[100005][2];
int work(int l,int r,int x)
{
	return (1ll*(x-l+1+x-r+1)*(r-l+1)/2)%p;
}
int quick(int x,int y)
{
	int s=1;
	while(y)
	{
		if(y&1)
		{
			s=1ll*s*x%p;
		}
		x=1ll*x*x%p;
		y=y/2;
	}
	return s;
}

int main()
{
	//freopen("mean.in","r",stdin);
	//freopen("mean.out","w",stdout);
	int n;
	scanf("%d",&n);
	int L=0,R=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&a[i].x,&a[i].y);
		L=max(L,a[i].x);
		R=max(R,a[i].y);
	}
	int ans=0;
	for(int x=L;x<=R;x++)
	{
		f[0][0]=1;
		for(int i=1;i<=n;i++)
		{
			f[i][0]=1ll*f[i-1][0]*work(a[i].x,min(x-1,a[i].y),x)%p;
			f[i][1]=1ll*f[i-1][1]*work(a[i].x,min(x,a[i].y),x)%p;
			if(a[i].x<=x&&x<=a[i].y)
			{
				f[i][1]=(f[i][1]+f[i-1][0])%p;
			}
			
		}
		ans=(ans+f[n][1])%p;
	}
	int ans1=1;
	for(int i=1;i<=n;i++)
	{
		ans1=1ll*ans1*quick(a[i].y-a[i].x+1,p-2)%p;
	}
	ans=1ll*ans*ans1%p;
	printf("%d\n",ans);
	return 0;
}