APIO2016 划艇 计数DP
题意
给出序列\(a,b\)，要求有多少个序列满足\(c_i = 0\)或者\(a_i \le c_i \leq b_i\) \((0 < a_i \leq b_i)\) 其中要求非\(0\)部分严格递增
\[1 \leq N \leq500\1 \leq a_i \leq b_i \leq10^9
\]
分析
考虑直接\(dp\)
\(dp[i][j]\)表示前\(i\)个数中，第\(i\)个数非0，且选择\(j\)的方案数
答案就是\(\sum_i \sum_j dp[i][j]\)
转移
\[dp[0][1] = 1\dp[i][j] = \sum_{p = 0}^{i - 1}\sum_{k = 0}^{j - 1}dp[p][k] ,(a_i \leq j \leq b_i)
\]
也就是考虑上一个选择的位置和大小转移
问题在于第二维到了\(10^9\)
这里就用到了技巧：离散化
先把点离散化，点构成了若干个新的区间
于是\(dp[i][j]\)表示选前\(i\)个数且第\(i\)个数非\(0\)，落在区间\(j\)上的方案数
注意这里相当于一次性求出了区间的所有方案，因此转移方程也有所改变
转移时，若干块的数会在同意区间，因此枚举落在区间\(j\)的方案数，需要考虑第\(p + 1\)个数到\(i\)的落在区间\(j\)的方案数
这类似于从\([0,L]\)中取\(n\)个数，且所有非零数严格递增，容易证明这样的方案数是\(\tbinom{L + n}{n}\)的
设\(m\)表示\(p + 1\)到\(i\)中能够落在区间\(j\)的个数，那么考虑这一段的组合
\[dp[i][j] = \sum_{p = 0}^{i - 1}\sum_{k = 0}^{j - 1}\tbinom{L + m - 1}{m} dp[p][k]
\]
将枚举到的区间作为阶段，此时\(m\)不变，于是显然可以对\(dp[p][k]\)做前缀和
令
\[g[i][j] = \sum_{k =1}^{j - 1}f[i][k]
\]
于是
\[dp[i][j] = \sum_{p = 0}^{i - 1} \tbinom{L + m - 1}{m} g[p][j - 1]
\]
实现起来的话注意一下离散化区间的细节，还有提前递推好组合数省一个\(log\)
代码
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define re register
using namespace std;
typedef long long ll;
int rd(){
int x = 0;
char ch = getchar();
while(ch < ‘0‘ || ch > ‘9‘) {
ch = getchar();
}
while(ch >= ‘0‘ && ch <= ‘9‘) {
x = x * 10 + ch - ‘0‘;
ch = getchar();
}
return x;
}
const int maxn = 505;
const ll MOD = 1e9 + 7;
int num[maxn << 1],a[maxn],b[maxn],c[maxn],iv[maxn];
int g[maxn];
int tot;
int main(){
int n = rd();
iv[1] = 1;
for(int i = 2;i <= n;i++) iv[i] = (ll)(MOD - MOD / i) * iv[MOD % i] % MOD;
for(int i = 1;i <= n;i++){
a[i] = rd();
b[i] = rd();
num[++tot] = a[i];
num[++tot] = b[i] + 1;
}
sort(num + 1,num + tot + 1);
for(int i = 1;i <= n;i++){
a[i] = lower_bound(num + 1,num + 1 + tot,a[i]) - num;
b[i] = lower_bound(num + 1,num + 1 + tot,b[i] + 1) - num;
}
c[0] = 1;
g[0] = 1;
for(int j = 1;j < tot;j++){
int len = num[j + 1] - num[j];
for(int i = 1;i <= n;i++) c[i] = (ll)c[i - 1] * (len + i - 1) % MOD * (iv[i] % MOD) % MOD;
for(int i = n;i;i--){
if(a[i] <= j && j + 1 <= b[i]) {
int f = 0;
int m = 1;
int C = len;
for(int p = i - 1;p >= 0;p--){
f += (ll)C * g[p] % MOD;
f %= MOD;
if(a[p] <= j && j + 1 <= b[p]) C = c[++m];
}
g[i] += f;
g[i] %= MOD;
}
}
}
int ans = 0;
for(int i = 1;i <= n;i++)
ans += g[i],ans %= MOD;
printf("%d",ans);
}