P3643 [APIO2016]划艇
题意
一个合法序列可表示为一个长度为 \(n\)
的序列，其中第 \(i\) 个数可以为 0 或
\([l_i,r_i]\)
中一个整数，且满足所有不为零的数组成的子序列严格上升。求合法序列方案数。\(n\leq 500,l_i\leq r_i\leq 10^9\)。
思路
朴素动态规划做法为，设 \(f_{ij}\)
表示第 \(i\) 个数不为零且数量为 \(j\) 且后面全选 0 的方案数，则 \[
ans=\sum_{i=1}^n\sum_{j=l_i}^{r_i}f_{ij}\\
f_{ij}=\sum_{k=1}^{j-1}\sum_{q=0}^{i-1}f_{qk},j\in[l_i,r_i]
\] 但是第二维枚举太多。考虑优化。
首先，我们考虑一段区间，按照上面的方式递推需要依次枚举数量再枚举
\(i-1\)
个数的方案进行转移，不能够简化的主要原因是因为每个数都有一个限定的区间。若不加限定，发现这段转移可以简化为一个简单问题：每个数可以选取值范围内任意的值或
0，求所有不为零的数组成的子序列严格上升方案数。设取值区间大小为 \(len\)，数的数量为 \(n\)，则答案为 \(\binom{len+n}n\)。可以理解为额外增加 \(n\) 个 0 表示选 0。
所以我们进行离散化，将取值范围分为若干段，每个数的范围由若干这样的段组成。对于每一段我们都可以按照上面的方法转移。即对于这一段区间
\(j\)，对于所有包含它的数字，可以从
\(0\) 到 \(i-1\) 中任意一种状态 \(k\) 转移得到，并且需要乘上在 \(k\) 到 \(i\) 中选任意个区间包含 \(j\) 的数字不为 0 的方案数，即 \(\binom{len+m-1}m\) 其中 \(m\) 为上述数的个数，\(len\) 为第 \(j\) 段的长度，减 1 是因为第 \(i\) 个必选。即 \[
ans=\sum_{i=1}^n\sum_{j=l_i}^{r_i}f_{ij}\\
f_{ij}=\sum_{q=0}^{i-1}\binom{len+m_{jq}-1}{m_{jq}}\sum_{k=1}^{j-1}f_{qk},j\in[l_i,r_i],m_{jq}=\sum_{o=q+1}^i[j\in[l_o,r_o]],len为区间j的长度
\] 发现后面的求和维护一个前缀和即可。总时间复杂度 \(O(n^3)\)。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<cmath>
using namespace std;
inline int read(){
int w=0,x=0;char c=getchar();
while(!isdigit(c))w|=c=='-',c=getchar();
while(isdigit(c))x=x*10+(c^48),c=getchar();
return w?-x:x;
}
namespace star
{
const int maxn=505,mod=1e9+7;
int n,m,l[maxn],r[maxn],b[maxn<<1],C[maxn],inv[maxn],f[maxn],ans;
inline void work(){
n=read();
inv[1]=1;for(int i=2;i<=n;i++) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
for(int i=1;i<=n;i++) l[i]=b[(i<<1)-1]=read(),r[i]=b[i<<1]=read(),b[i<<1]++;
sort(b+1,b+1+(n<<1));
m=unique(b+1,b+1+(n<<1))-b-1;
for(int i=1;i<=n;i++) l[i]=lower_bound(b+1,b+1+m,l[i])-b,r[i]=lower_bound(b+1,b+1+m,r[i]+1)-b;
C[0]=f[0]=1;
for(int j=1;j<m;j++){
int len=b[j+1]-b[j];
for(int i=1;i<=n;i++) C[i]=1ll*C[i-1]*(len+i-1)%mod*inv[i]%mod;
for(int i=n;i;i--) if(l[i]<=j and r[i]>=j+1){
int cnt=1;
for(int k=i-1;~k;k--) f[i]=(f[i]+1ll*C[cnt]*f[k])%mod,cnt+=l[k]<=j and r[k]>=j+1;
}
}
for(int i=1;i<=n;i++) ans=(ans+f[i])%mod;
printf("%d\n",ans);
}
}
signed main(){
star::work();
return 0;
}
|
