- 有(n)个位置，第(i)个位置可以选择填入([a_i,b_i])中的某个数或者填入(-1)，要求所有不是(-1)的数严格递增。
- 求有多少种可能的序列。
- (nle500)
这道题本来想了挺久却一直想错了方向，后来得到一个需要离散化的提示就立刻秒掉了。。。
果然我现在做题最主要的问题是一开始就会把做题方向搞错，结果只会在错误道路上越走越远。
离散化+动态规划
方便起见先把所有(b_i)加(1)，让每个位置能填的数变成一个左闭右开区间，然后就能很开心地离散化了。
记排序去重后第(j)个数为(dv_j)。
设(f_{i,j})表示第(i)个位置选择填入一个([0,dv_{j+1}))的数时前(i)个位置的方案数。
我们可以先求出第(i)个位置选择填入一个([dv_j,dv_{j+1}))中的数时的方案数(f'_{i,j})，则只要最后做一遍前缀和就可以求出真正的(f_{i,j})了。
考虑到离散化之后的一个核心烦点就是每个(j)对应着一段值域区间([dv_j,dv_{j+1}))，我们无法确定一个位置填入的究竟是其中的哪个数。
因此，我们需要对所有填入这段区间中的数的位置一起转移，即枚举一个(k)，表示(k)是最后一个填入了([0,dv_j))中的数的位置，也就意味着有且仅有([k+1,i])中所有选择填数的位置填入了([dv_j,dv_{j+1}))中的数字。
如果我们从(i-1)开始往前枚举(k)，可以方便地统计出一个(t)表示([k+1,i])中离散化后(jin[a_x,b_x))位置个数。
由于这(t)个位置不一定全要填数，我们枚举选择了(x)个位置填数，那么填入的数就有(C_{dv_{j+1}-dv_j}^x)种选法，选择填数的位置就有(C_{t-1}^{x-1})种选法（这里减(1)是因为(i)是必选位置）。
综上所述，我们的转移方程应该是：
这样子得到的是一个(O(n^4))复杂度的解法，但发现后面(sum)中的东西完全与(i)无关，因此我们可以先枚举(j,t,x)预处理出一个(g_{j,t})表示这玩意儿，那么实际(DP)的时候就不用再枚举(x)了，复杂度正确。
代码：(O(n^3))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 500
#define X 1000000007
using namespace std;
int n,a[N+5],b[N+5],dc,dv[2*N+5],f[N+5][2*N+5],g[2*N+5][N+5],C[N+5][N+5],C_[2*N+5],Inv[N+5];
int main()
{
RI i,j,k;for(scanf("%d",&n),i=1;i<=n;++i) scanf("%d%d",a+i,b+i),dv[i]=a[i],dv[i+n]=++b[i];//右端点加1变左闭右开
#define GV(x) (lower_bound(dv+1,dv+dc+1,x)-dv)
for(sort(dv+1,dv+2*n+1),dc=unique(dv+1,dv+2*n+1)-dv-1,i=1;i<=n;++i) a[i]=GV(a[i]),b[i]=GV(b[i]);//离散化
for(Inv[1]=1,i=2;i<=n;++i) Inv[i]=1LL*(X-X/i)*Inv[X%i]%X;//预处理逆元
for(C[0][0]=i=1;i<=n;++i) for(C[i][0]=j=1;j<=i;++j) C[i][j]=(C[i-1][j-1]+C[i-1][j])%X;//预处理n以内的C[i][j]
RI d;for(i=1;i^dc;++i)
{
for(d=dv[i+1]-dv[i],C_[0]=j=1;j<=min(n,d);++j) C_[j]=1LL*C_[j-1]*Inv[j]%X*(d-j+1)%X;//预处理C[dv[i+1]-dv[i]][j]
for(j=1;j<=n;++j) for(k=1;k<=min(j,d);++k) g[i][j]=(g[i][j]+1LL*C_[k]*C[j-1][k-1])%X;//计算辅助数组g[i][j]
}
RI t;for(i=0;i<=dc;++i) f[0][i]=1;for(i=1;i<=n;++i)//枚举每个位置
{
for(j=a[i];j^b[i];++j) for(k=i-1,t=1;~k;--k) f[i][j]=(f[i][j]+1LL*f[k][j-1]*g[j][t])%X,a[k]<=j&&j<b[k]&&++t;
//枚举最后一个填入[0,dv[j])的位置k，记录t表示[k+1,i]中j∈[a[x],b[x])的位置数
for(j=1;j<=dc;++j) f[i][j]=(f[i][j]+f[i][j-1])%X;//前缀和
}
for(t=0,i=1;i<=n;++i) t=(t+f[i][dc])%X;return printf("%d
",t),0;
}