题目链接

题目大意

给你一个长度为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个数

$0,0,\dots 0,0,1,2,3,\dots L-1,L$

前面总共有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这个区间中。
根据我们上面的结论，转移即为

$f_{i,j}=\sum\limits_{k=0}^{i-1}\binom{L+t}{t}\sum\limits_{p=1}^{j-1}f_{k,p}$

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

$ans=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{\infty}f_{i,j}$

代码

#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;
}