[Luogu 3643] [APIO2016] 划艇

Posted on | In , | Views:

题目链接

Luogu 3643

题目大意

给你一个长度为n的数列，数列第i项可以取$[l_i,r_i]$，或者不取，使得最后取的数单调递增，问方案数，若所有数均不取不计入方案。
$n\le 500,l_i\le r_i\le 1e9$

做法

我们先考虑这样一个问题，一个长度为n的数列，数列的每个数可以取$[1,L]$，使得数列单调递增的方案数。那么这个答案显然是$\binom{L}{n}$，当你选的数确定后，放的位置也自然就确定了。
接下来将问题改为一个长度为n的数列，数列的每个数可以取$[1,L]$或不取，使得最后取的数单调递增的方案数。
假设我们从这样一个数列中取n个数

前面总共有n个0。
我们将每种取数的方案如下映射到一个数列上。
如果取到第i个0，那么数列的第i位不取。
剩下取到的非0的数按照升序依次填入取的位即可。
这个映射显然是个双射，所以我们要求的答案即为$\binom{n+L}{n}$
那么知道了这个有什么用呢？
我们先将原先的值域离散成若干段左开右闭的区间，那么$[l_i,r_i]$就表示若干段左开右闭的区间了。
考虑dp
用$f_{i,j}$表示数列的前i项，第i项取在j这个区间中的方案数。
再枚举k，表示数列的第k项取，并且取的区间小于j。
也就是说数列的$[k+1,i-1]$这些要么不取，要么全部取在j这个区间中。
根据我们上面的结论，转移即为

$L$表示$j$这段开区间的长度，t表示$[k+1,i]$中有多少个位置，能取的范围是包括$j$这段开区间的，(如果不包括，显然只能不取)
对于后面这个式子我们用前缀和优化。
k从大往小枚举，组合数可以$O(1)$递推。
最后求答案并非是$\sum\limits_{j=1}^{\infty} f_{n,j}$，因为第n项可以不取，而$f_{i,j}$中i这一项是必须取的。
所以我们考虑最后取的是哪一项，后面的都不取

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define N (505)
using namespace std;
int n,ans,t; 
int l[N],r[N],q[N<<1],f[N][N<<1],sum[N][N<<1],inv[N<<1];
const int P=1000000007;
template <typename T> void read(T&t) {
    t=0;
    bool fl=true;
    char p=getchar();
    while (!isdigit(p)) {
        if (p=='-') fl=false;
        p=getchar();
    }
    do {
        (t*=10)+=p-48;p=getchar();
    }while (isdigit(p));
    if (!fl) t=-t;
}
inline int Inc(int a,int b){
    return (a+b>=P)?(a+b-P):(a+b);
}
int main(){
    read(n);
    for (int i=1;i<=n;i++){
        read(l[i]),read(r[i]);
        q[++t]=l[i],q[++t]=r[i]+1; 
    } 
    sort(q+1,q+t+1);
    t=unique(q+1,q+t+1)-q-1;
    inv[0]=inv[1]=1;
    for (int i=2;i<=n;i++){
        inv[i]=Inc(1ll*-P/i*inv[P%i]%P,P);
    }
    for (int i=1;i<=n;i++){
        l[i]=lower_bound(q+1,q+t+1,l[i])-q;
        r[i]=lower_bound(q+1,q+t+1,r[i]+1)-q-1;
    }
    f[0][0]=1;
    for (int j=0;j<=t;j++) sum[0][j]=1;
    for (int i=1;i<=n;i++){
        for (int j=l[i];j<=r[i];j++){
            int fw=q[j+1]-q[j],C=fw,x=fw,y=1;
            for (int k=i-1;k>=0;k--){
                f[i][j]=Inc(f[i][j],1ll*sum[k][j-1]*C%P);
                if (l[k]<=j&&r[k]>=j){
                    C=1ll*C*(x+1)%P*inv[y+1]%P;
                    x++,y++;
                }
            }
        }
        //for (int j=1;j<=t;j++) printf("%d %d %d\n",i,j,f[i][j]);
        sum[i][0]=f[i][0];
        for (int j=1;j<=t;j++) sum[i][j]=Inc(sum[i][j-1],f[i][j]);  
    }
    for (int i=1;i<=n;i++) ans=Inc(ans,sum[i][t]);
    printf("%d",ans);
    return 0;
}