牛客小白月赛23f美丽的序列I，数学+分类
美丽的序列I
https://ac.nowcoder.com/acm/contest/4784/F
一个不降序列本身度是1，要分成若干不降，那么每降的地方就分割一次，所以就转变成求序列有多少前>后——分割次数
一个确定数列的美丽度=1+分割次数
1是每个数列都要加的，分割次数不确定（可能为0）
所有的1的和=可以排成的数列方案数
分割次数和=（遍历每两个相邻数）ai>ai+1的组合数*贡献（即不考虑这两个位置，其他位置的组合数）
前的情况大概怎么几种
情况-1，-2是没有前<后的
特别注意情况1和2是不同的
2中6有5种方法，5只有4种方法
先算斜阴影，
再算竖阴影，因为是点的方法连续递增1，所以（最大+最少）*数量 求和
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7,N=1e5+10;
ll n,inv2,l[N],r[N],pro[N],repro[N],pl,pr,el,er,ans,big,small,num;
ll qmi(ll a,ll b,ll mod){
ll ans=1;
while(b){
if(b&1) ans=ans*a%mod;
b>>=1;
a=a*a%mod;
}
return ans;
}
int main(){
cin>>n;
inv2=qmi(2,mod-2,mod);
for(int i=1;i<=n;i++){
cin>>l[i]>>r[i];
}
pro[0]=1; for(int i=1;i<=n;i++) pro[i]=pro[i-1]*(r[i]-l[i]+1)%mod;
repro[n+1]=1; for(int i=n;i>=1;i--) repro[i]=repro[i+1]*(r[i]-l[i]+1)%mod;
ans=pro[n];
for(int i=2;i<=n;i++){
pl=l[i-1], pr=r[i-1];
el=l[i], er=r[i];
if(pr<=el) continue;
if(pl>er){//情况1
ans=(ans+(er-el+1)*(pr-pl+1)%mod*pro[i-2]%mod*repro[i+1]%mod)%mod;
continue;
}
if(pr>er){//斜阴影
ans=(ans+(pr-er)*(er-el+1)%mod*pro[i-2]%mod*repro[i+1]%mod)%mod;
pr=er;
}
//竖阴影
big=pr-el; small=max(pl-el,0LL);
num=big-small+1;
ans=(ans+(big+small)*num%mod*inv2%mod*pro[i-2]%mod*repro[i+1]%mod)%mod;
}
cout<<ans;
return 0;
} 创作不易
投递字节跳动等公司10个岗位
