P3643 [APIO2016]划艇 dp+组合数
标签：isp onclick https display bit view splay class uniq
题意：
有n个数，每个数有取值范围[ai,bi]，问能取多少个递增子序列（长度不限）
题解:
https://www.luogu.com.cn/problemnew/solution/P3643
#includeusing 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;imod;
for(int i=1;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) {
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) {
int len=num[j+1]-num[j];
for(int i=1;i)
C[i]=C[i-1]*(len+i-1)%mod*inv[i]%mod;
for(int i=n;i>=1;i--) if(a[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]1m];
}
g[i]=(g[i]+f)%mod;
}
}
ll ans=0;
for(int i=1;imod;
coutans;
}
View Code
P3643 [APIO2016]划艇 dp+组合数
标签：isp onclick https display bit view splay class uniq
原文地址：https://www.cnblogs.com/bxd123/p/12247114.html
评论