总共只有2*n段。分段进行DP
简单的方法是：
外层枚举段数j，f[i]表示，当前枚举到j的时候，以(i,j)结尾（必须选择(i,j)）的方案数，枚举一个f(p,1~j-1)进行转移
连续一段j区间，有包括i一共有m个可以选择的学校，那么这里贡献的方案数就是：∑(1<=i<=m)C(len,i)*C(m-1,i)=C(l+m-1,m)等式考虑用网格图走来证明
C可以预处理
#include<bits/stdc++.h> #define reg register int #define il inline #define fi first #define se second #define mk(a,b) make_pair(a,b) #define numb (ch^'0') using namespace std; typedef long long ll; template<class T>il void rd(T &x){ char ch;x=0;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x); } template<class T>il void output(T x){if(x/10)output(x/10);putchar(x%10+'0');} template<class T>il void ot(T x){if(x<0) putchar('-'),x=-x;output(x);putchar(' ');} template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar(' ');} namespace Miracle{ const int N=1003; const int mod=1e9+7; int n; int lo[N],hi[N],c[2*N],cnt; int C[N]; int ad(int x,int y){ return x+y>=mod?x+y-mod:x+y; } int mul(int x,int y){ return (ll)x*y%mod; } int g[N]; int inv[N]; int main(){ rd(n); inv[1]=1; for(reg i=2;i<=n;++i){ inv[i]=mul(mod-mod/i,inv[mod%i]); } for(reg i=1;i<=n;++i){ rd(lo[i]);rd(hi[i]); c[++cnt]=lo[i];c[++cnt]=hi[i]+1; } sort(c+1,c+cnt+1); cnt=unique(c+1,c+cnt+1)-c-1; for(reg i=1;i<=n;++i){ lo[i]=lower_bound(c+1,c+cnt+1,lo[i])-c; hi[i]=lower_bound(c+1,c+cnt+1,hi[i]+1)-c; } g[0]=1;C[0]=1; // cout<<" cnt "<<cnt<<endl; // prt(lo,1,n); // prt(hi,1,n); for(reg j=1;j<cnt;++j){ int len=c[j+1]-c[j]; // cout<<" len "<<len<<" in "<<j<<endl; C[0]=len; for(reg i=1;i<=n;++i) C[i]=mul(C[i-1],mul(len+i,inv[i+1])); // cout<<" C ";prt(C,0,n); for(reg i=n;i>=1;--i){ if(lo[i]<=j&&j<hi[i]){ int f=0,m=0; for(reg p=i-1;p>=0;--p){ f=ad(f,mul(C[m],g[p])); if(lo[p]<=j&&j<hi[p]) ++m; } g[i]=ad(g[i],f); // cout<<" con "<<i<<" "<<f<<endl; } } // cout<<"gg "<<endl; // prt(g,1,n); } int ans=0; for(reg i=1;i<=n;++i) ans=ad(ans,g[i]); ot(ans);return 0; } } signed main(){ Miracle::main(); return 0; } /* Author: *Miracle* */