题解
一种思路很好想：(f_{i,j}) 表示前 (i) 所学校中，第 (i) 所学校参赛且派出 (j) 艘划艇的方案数。（转移就不列了。）
这种方式有一个致命点，就是 (j) 的范围是 (10^9)，这样连 (9) 分都过不去。当我们看到这么大数据范围时，一般想的都是离散化。
此时我们就可以设状态为：(f_{i,j}) 表示前 (i) 所学校中第 (i) 所学校参赛，且派出的划艇数落到第 (j) 个区间的方案数。因为一共有 (n) 个区间，所以 (j) 复杂度最多为 (mathcal O(n))。
所以在第 (i) 所学校之前的学校可以分为两种，在区间 (j) 的和不在的。
引理 ：
若要从 ([0,L]) 中选出 (n) 个数，其中非零数严格递增，则有 ((^{L+n}_{kern 0.6em n})) 种可能
（证明请看别的大佬的题解）
那么对于本题来说，因为我们设的第 (i) 所学校必须参赛，所以计算 (0) 时答案需要减 (-1) ，方案数即为 ((^{m-1+L}_{;;; m}))，(m) 表示挑选划艇个数在第 (j) 个区间的学校的数量。
那么转移方程容易得出：
[f_{i,j}=left{
egin{array}{l}
sum_{p=1}^{i-1}sum_{k=1}^{j-1}(^{m+L-1}_{;;; m})f_{p,k} kern 1.5emjin [a_i,b_i] \
0 kern 10.8emj
otin [a_i,b_i]\
end{array}
ight.
]
对于 (sum_{p=1}^{i-1}sum_{k=1}^{j-1}(^{m+L-1}_{;;; m})f_{p,k}) 我们可以用一个前缀和处理一下
则设 (g_{i,j}=sum_{k=1}^{j}f_{i,k})
那么最后的转移为
[f_{i,j}=sum_{p=1}^{i-1}(^{m+L-1}_{;;; m})g_{p,j-1} ;;; jin[a_i,b_i]
]
Code
#include<bits/stdc++.h>
#define ri register int
#define p(i) ++i
using namespace std;
namespace IO{
char buf[1<<21],*p1=buf,*p2=buf;
inline char gc() {return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline int read() {
ri x=0,f=1;char ch=gc();
while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();}
while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
return x*f;
}
}
using IO::read;
namespace nanfeng{
#define ll long long
static const int N=550;
static const int MOD=1e9+7;
int inv[N],a[N],b[N],num[N<<1],C[N],g[N],tot,n;
inline int main() {
n=read();
inv[1]=1;
for (ri i(2);i<=n;p(i)) inv[i]=1ll*(MOD-MOD/i)*inv[MOD%i]%MOD;
for (ri i(1);i<=n;p(i)) {
a[i]=read(),b[i]=read();
num[p(tot)]=a[i];num[p(tot)]=b[i]+1;
}
sort(num+1,num+tot+1);
tot=unique(num+1,num+tot+1)-num-1;
for (ri i(1);i<=n;p(i)) {
a[i]=lower_bound(num+1,num+tot+1,a[i])-num;
b[i]=lower_bound(num+1,num+tot+1,b[i]+1)-num;
}
C[0]=g[0]=1;
for (ri j(1);j<tot;p(j)) {
int len=num[j+1]-num[j];
for (ri i(1);i<=n;p(i)) C[i]=(ll)C[i-1]*(ll)(len+i-1)%MOD*inv[i]%MOD;
for (ri i(n);i;--i) {
if (a[i]<=j&&j+1<=b[i]) {
int f=0,cnt=1,l=C[1];
for (ri k(i-1);k>=0;--k) {
f=(f+(ll)l*g[k]%MOD)%MOD;
if (a[k]<=j&&j+1<=b[k]) l=C[p(cnt)];
}
g[i]=(g[i]+f)%MOD;
}
}
}
int ans=0;
for (ri i(1);i<=n;p(i)) ans=(ans+g[i])%MOD;
printf("%lld
",ans);
return 0;
}
// #undef int
}
int main() {return nanfeng::main();}
复杂度为 (mathcal O(n^3))