P3643
好题捏。
首先容易想到的状态是设 \(f_{i,j}\) 表示对于前 \(i\) 个数，第 \(i\) 个数取 \(j\) 的方案总数，但这个 \(j\) 的值最大可以取到 \(10^9\)，这种思路肯定是不行的。
那么很自然地去想到离散化，然后得到了若干个值域段（最多 \(2n\) 个）。我们考虑设 \(f_{i,j}\) 表示对于前 \(i\) 个数，第 \(i\) 个数在第 \(j\) 个值域段的方案总数。
则我们考虑去枚举一个 \(k\)，然后前 \(1\sim k-1\) 个在前 \(j-1\) 个段里乱选，第 \(k\sim i\) 个在第 \(j\) 段里选。容易得到的是，前者贡献为 \(\sum\limits_{x=1}^{j-1} f_{k-1,j}\)；后者似乎是 \(len_j\choose i-k+1\)，但其实并不然，每个数还可以不选，如果说我们考虑记不选为 \(-1\)，且有 \(m\) 个可以在第 \(j\) 段选（即 \(j\in[a_k,b_k]\)），则等价于在下面几个数当中选 \(m\) 个：
\[\underbrace{-1,-1,\cdots,-1}_{m-1\text{个}},1,2,\cdots,len_j
\]
需要注意的是，\(-1\) 的个数应当是 \(m-1\) 而非 \(m\) 个，因为第 \(i\) 个数必须选。
则得到转移方程：
\[f_{i,j}=\sum\limits_{k=1}^i {len_j+m-1 \choose m}\sum\limits_{x=1}^{j-1} f_{k-1,j}
\]
其中后面那个 \(\sum\) 显然可以前缀和优化掉，然后组合数也可以在每次 \(m\) 增加时顺手转移，所以最终得到复杂度为 \(\Theta(n^3)\)。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
using namespace std;
const int N=1e3+5,MOD=1e9+7;
int t[N],a[N],b[N],g[N][N],f[N][N],C[N],len,n;
int jc[N],inv_jc[N],inv[N];
int qpow(int a,int b) {
int res=1,base=a;
while(b) {
if(b&1)
res=res*base%MOD;
base=base*base%MOD; b>>=1;
}
return res;
}
void init() {
jc[0]=1;
rep(i,1,n)
jc[i]=jc[i-1]*i%MOD;
inv_jc[n]=qpow(jc[n],MOD-2);
per(i,n-1,0)
inv_jc[i]=inv_jc[i+1]*(i+1)%MOD;
rep(i,1,n)
inv[i]=inv_jc[i]*jc[i-1]%MOD;
}
int get_id(int x) {
return lower_bound(t+1,t+len+1,x)-t;
}
void add(int &a,int b) {
a+=b;
if(a>=MOD)
a-=MOD;
}
signed main() {
scanf("%lld",&n); init();
rep(i,1,n) {
scanf("%lld%lld",&a[i],&b[i]); ++b[i];
t[++len]=a[i];
t[++len]=b[i];
}
sort(t+1,t+len+1);
len=unique(t+1,t+len+1)-t-1;
rep(i,1,n)
a[i]=get_id(a[i]),b[i]=get_id(b[i]);
C[0]=g[0][0]=1;
rep(j,1,len-1) {
int l=t[j+1]-t[j];
rep(i,1,n)
C[i]=C[i-1]*(l+i-1)%MOD*inv[i]%MOD;
rep(i,0,n)
g[i][j]=g[i][j-1];
rep(i,1,n) {
if(a[i]<=j&&j+1<=b[i]) {
int tot=0,mul=0;
mul=C[++tot];
per(k,i-1,0) {
add(f[i][j],mul*g[k][j-1]%MOD);
if(a[k]<=j&&j+1<=b[k])
mul=C[++tot];
}
add(g[i][j],f[i][j]);
}
}
}
int ans=0;
rep(i,1,n)
add(ans,g[i][len-1]);
printf("%lld\n",ans);
return 0;
}