题解 CF1295F 【Good Contest】
xht
2020-01-30 21:39:48
题意即 $a_i$ 在 $[l_i, r_i]$ 等概率随机，求 $a_{1 \dots n}$ 不增的概率。
跟 [P3643 [APIO2016]划艇](https://www.luogu.com.cn/problem/P3643) 几乎一样：$a_i$ 在 $[l_i, r_i]$ 等概率随机，也可以跳过，求形成的序列递增的方案数。
先考虑这题。
首先将区间离散化成若干个左闭右开的区间。
设 $f_{i, j}$ 表示考虑到 $a_i$，$a_i$ 在第 $j$ 个区间内的方案数。
枚举上一个在 $j$ 之前的位置 $a_k$ 转移。
设 $k + 1 \sim i$ 中有 $c$ 个位置可以选择第 $j$ 个区间，设第 $j$ 个区间的长度为 $l_j$，则方案数为 $\binom{l_j + c}{c}$。
需要前缀和优化，时间复杂度 $\mathcal O(n^3)$。
```cpp
const int N = 507;
int n, a[N], b[N], c[N*2], t;
modint f[N], g[N], ans;
int main() {
rd(n);
for (int i = 1; i <= n; i++)
rd(a[i]), rd(b[i]), c[++t] = a[i], c[++t] = ++b[i];
sort(c + 1, c + t + 1), t = unique(c + 1, c + t + 1) - (c + 1);
for (int i = 1; i <= n; i++)
a[i] = lower_bound(c + 1, c + t + 1, a[i]) - c,
b[i] = lower_bound(c + 1, c + t + 1, b[i]) - c;
f[0] = 1;
for (int j = 1; j < t; j++) {
int l = c[j+1] - c[j];
g[0] = 1;
for (int i = 1; i <= n; i++) g[i] = g[i-1] * (l + i - 1) / i;
for (int i = n; i; i--)
if (a[i] <= j && j < b[i])
for (int c = 1, k = i - 1; ~k; k--) {
f[i] += g[c] * f[k];
if (a[k] <= j && j < b[k]) ++c;
}
}
for (int i = 1; i <= n; i++) ans += f[i];
print(ans);
return 0;
}
```
再来看原题就很简单了，照着做即可。
```cpp
const int N = 57;
int n, a[N], b[N], c[N*2], t;
modint f[N], g[N], ans;
int main() {
rd(n);
for (int i = 1; i <= n; i++)
rd(a[i]), rd(b[i]), c[++t] = a[i], c[++t] = ++b[i];
sort(c + 1, c + t + 1), t = unique(c + 1, c + t + 1) - (c + 1);
for (int i = 1; i <= n; i++)
a[i] = lower_bound(c + 1, c + t + 1, a[i]) - c,
b[i] = lower_bound(c + 1, c + t + 1, b[i]) - c;
f[0] = 1;
for (int j = t - 1; j; j--) {
int l = c[j+1] - c[j];
g[0] = 1;
for (int i = 1; i <= n; i++) g[i] = g[i-1] * (l + i - 1) / i;
for (int i = n; i; i--)
if (a[i] <= j && j < b[i])
for (int c = 1, k = i - 1; ~k; k--, ++c) {
f[i] += g[c] * f[k];
if (a[k] > j || j >= b[k]) break;
}
}
ans = f[n];
for (int i = 1; i <= n; i++) ans /= c[b[i]] - c[a[i]];
print(ans);
return 0;
}
```