题解 | #美丽的序列I# 超详细题解

美丽的序列I

https://ac.nowcoder.com/acm/contest/4784/F

牛客4784F - 美丽的序列I

链接：https://ac.nowcoder.com/acm/contest/4784/F

知识点：组合计数、贡献

难度：蓝

题意

给出一个长度为 $n$ 的序列。再给出 $n$ 个 $l_{i}$ ， $r_{i}$ 。意思是 $a_{i}$ 是 $[l_{i}, r_{i}]$ 中的随机一个，并且出现的概率一致。
如果一个序列出现 $a_i>a_{i+1}$ ，那么就在i和i+1之间将序列断开。定义一个序列的美丽值为该序列最终的段数（如果一次也没有从中间分断过，那么美丽值为1）。
求出所有可能出现的序列，这些序列的美丽值之和，答案对 $1 0^{9} + 7$ 取模。
$n < = 1 0^{5}$ ， $1 < = l_{i} < = r_{i} < = 1 0^{9}$

思路

序列中每个数达到了 $1 0^{9}$ ，并且 $n$ 也很大，因此不能使用DP。
继续看题，需要求的是所有可能出现的序列的美丽值之和。
那么，考虑每个可能产生分断的情况对答案的贡献。
对于某一个 $a_{i} < a_{i} + 1$ 的情况，它对答案的贡献是： $(\prod_{1}^{i-1}a_i)\times(\prod_{i+2}^{n}a_i)$
我们观察到，上面提到的贡献只跟 $a_{i} < a_{i} + 1$ 的这个 $i$ 有关，跟 $a_{i}$ 和 $a_{i+1}$ 的取值无关。
那么我们接下来要计算 $i$ ～ $i + 1$ 之间产生了多少个 $a_{i} < a_{i} + 1$ ，用这个数量乘以上面提到的贡献。

如何计算 $i$ ～ $i + 1$ 之间产生了多少个 $a_{i} < a_{i} + 1$ ？

显然需要手推式子，这个式子需要用到等差数列求和。

最后

这样还不够，还没加上从开头到分断点之间的那部分，这一部分是： $\prod_{1}^{n}(r_i-l_i+1)$

代码

#include <cstdio>
#include <iostream>
#define int long long
const int N	= 1e6+10;
const int MOD	= 1e9+7;
using namespace std;

long long POW(long long a,long long b)
{
	long long ans=1;
	while(b>0)
	{
		if(b&1)
		{
			ans*=a;
			ans%=MOD;
		}
		a*=a;
		a%=MOD;
		b>>=1;
	}
	return ans;
}
int Div(int a,int b)
{
	return a * POW(b, MOD-2) % MOD;
}
int AP_SUM(int l,int r)
{
	if(r==0)return 0;
	int len = r-l+1;
	return Div(len*((l+r)%MOD)%MOD, 2ll);
}

int Li[N],Ri[N];
int mul = 1;
int n;

void Solve()
{
	int ans = mul;
	for (int i=n-1; i>=1; i--)
	{
		int st = min(max(Li[i]-Li[i+1],1ll),Ri[i+1]-Li[i+1]+1);
		int ed = min(max(Ri[i]-Li[i+1],0ll), Ri[i+1]-Li[i+1]+1);
		
		int tmp = Div(mul, (Ri[i]-Li[i]+1) * (Ri[i+1]-Li[i+1]+1)%MOD );
		int tmp2 = max(0ll, min(Ri[i]-Ri[i+1]-1, Ri[i]-Li[i])) * (Ri[i+1]-Li[i+1]+1) % MOD;
		ans += (AP_SUM(st, ed)+tmp2) % MOD * tmp % MOD, ans%=MOD;
	}
	printf("%lld\n",ans);
}

signed main()
{
	scanf("%lld",&n);
	for (int i=1; i<=n; i++)
	{
		scanf("%lld %lld",&Li[i],&Ri[i]);
		
		mul *= Ri[i]-Li[i]+1, mul%=MOD;
	}
	Solve();
	
	return 0;
}