一种思路很好想:\(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\{
\begin{array}{l}
\sum_{p=1}^{i-1}\sum_{k=1}^{j-1}(^{m+L-1}_{\;\;\;\ m})f_{p,k} \kern 1.5emj\in [a_i,b_i] \\
0 \kern 10.8emj\notin [a_i,b_i]\\
\end{array}
\right.
\]
对于 \(\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} \;\;\;\ j\in[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\n",ans);
return 0;
}
// #undef int
}
int main() {return nanfeng::main();}
复杂度为 \(\mathcal O(n^3)\)
手机扫一扫
移动阅读更方便
你可能感兴趣的文章