题意:
有n个数,每个数有取值范围[ai,bi],问能取多少个递增子序列(长度不限)
题解:
https://www.luogu.com.cn/problemnew/solution/P3643
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=3e5+100; ll mod=1e9+7; int n; ll C[N],inv[N],a[N],b[N],ans,num[N],cnt,g[N],f[N]; int main() { cin>>n; inv[1]=1; for(int i=2;i<=n;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod; for(int i=1;i<=n;i++) { scanf("%lld%lld",&a[i],&b[i]); num[++cnt]=a[i]; num[++cnt]=b[i]+1; } sort(num+1,num+1+cnt); cnt=unique(num+1,num+1+cnt)-num-1; for(int i=1;i<=n;i++) { a[i]=lower_bound(num+1,num+1+cnt,a[i])-num; b[i]=lower_bound(num+1,num+1+cnt,b[i]+1)-num; } C[0]=1; g[0]=1; for(int j=1;j<cnt;j++) { int len=num[j+1]-num[j]; for(int i=1;i<=n;i++) C[i]=C[i-1]*(len+i-1)%mod*inv[i]%mod; for(int i=n;i>=1;i--) if(a[i]<=j&&b[i]>=j+1) { ll f=0,m=1,c=len; for(int p=i-1;p>=0;p--) { f=(f+c*g[p]%mod)%mod; if(a[p]<=j&&j+1<=b[p]) c=C[++m]; } g[i]=(g[i]+f)%mod; } } ll ans=0; for(int i=1;i<=n;i++) ans=(ans+g[i])%mod; cout<<ans; }