牛客4784F - 美丽的序列I

• 链接：https://ac.nowcoder.com/acm/contest/4784/F
• 知识点：组合计数、贡献
• 难度：蓝

题意

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

思路

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

如何计算 $ii$～$i+1i+1$ 之间产生了多少个 ？

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

最后

• 这样还不够，还没加上从开头到分断点之间的那部分，这一部分是：${\prod }_1^n(r_i-l_i+1)\backslash 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;
}