1. 问题分析与核心难点

• 题目要求：在 $N$ 所学校中选出若干所，每所学校 $i$ 派出 $c_i$ 艘划艇，满足 $c_i \in [a_i, b_i]$。如果学校 $i$ 和 $j$ ($i < j$) 都参加，则必须满足 $c_i < c_j$（严格递增）。
• 难点：$a_i, b_i$ 的范围非常大（$10^9$），无法直接作为 DP 的状态维度。但 $N$ 很小（$N \le 500$）。

2. 解决方案：离散化

由于只有 $N$ 个区间，涉及到的端点最多只有 $2N$ 个。我们可以将所有的 $a_i$ 和 $b_i+1$ 收集起来，排序去重。 这样就将整个数轴切分成了若干个左闭右开的小区间 $[p_k, p_{k+1})$。 在每一个小区间内，由于没有其他的边界点，所有学校在这个区间内的“可选性”是一样的（要么整个区间都能选，要么都不能选）。

代码对应部分：

// 收集端点
p[++p[0]] = l[i], p[++p[0]] = r[i]; // 注意输入时 r[i] 已经 +1 了
// 排序去重
sort(p + 1, p + p[0] + 1), p[0] = unique(p + 1, p + p[0] + 1) - p - 1;
// 重新映射 l[i] 和 r[i] 到离散化后的下标
l[i] = lower_bound(...) - p;
r[i] = lower_bound(...) - p;

3. 动态规划设计

我们定义 DP 状态。为了节省空间，代码中使用了一维数组滚动更新，但理解时我们可以按二维来思考。

设 $f[i][j]$ 表示：考察到了第 $i$ 个离散化区间，且序列中最后一个学校是 $j$（$j$ 选出的划艇数量落在区间 $i$ 内）的方案数。

这份代码中的 g[j] 实际上维护的是：在当前处理的区间之前的所有区间中，以学校 $j$ 结尾的方案总数（即划艇数量严格小于当前区间）。

4. 状态转移与组合数学

这是本题最精彩的部分。

当我们处理第 $i$ 个离散化区间（长度 $len = p_{i+1} - p_i$）时，我们枚举在这个区间内选出的最后一个学校 $j$。 同时，我们枚举上一个区间的结尾学校 $k$ ($k < j$)。此时，我们需要决定有哪些学校在这个区间内被选中。

假设在学校 $k$ 和 $j$ 之间（不含 $k$，含 $j$），共有 $cnt$ 个学校的允许范围 $[l_x, r_x]$ 覆盖了当前区间 $i$。 我们需要从这 $cnt$ 个学校中选出 $m$ 个（$1 \le m \le cnt$，且必须包含 $j$），并给它们分配区间内的数值，使得数值严格递增。

组合数推导：

1. 从 $cnt$ 个可选学校中选出 $m$ 个，其中 $j$ 必须被选中。方案数为 $\binom{cnt-1}{m-1}$。
2. 在长度为 $len$ 的区间内选出 $m$ 个不同的数，按大小分配给这 $m$ 个学校。方案数为 $\binom{len}{m}$。
3. 总贡献为：$$\sum_{m=1}^{cnt} \binom{cnt-1}{m-1} \binom{len}{m} $$根据组合恒等式 $\sum_{i=0}^n \binom{n}{i} \binom{M}{i+1} = \binom{M+n}{n+1}$，上式等价于：$$\binom{len + cnt - 1}{cnt}$$

代码对应部分：

// 预处理当前区间的组合数 C[x] = C(len + x - 1, x)
for (int j = 1; j <= n; j++)
    C[j] = 1ll * C[j - 1] * (len + j - 1) % mod * inv[j] % mod;

// DP 转移
for (int j = n; j; j--) { // 倒序枚举当前区间的结束学校 j
    if (r[j] < i + 1 || l[j] > i) continue; // 如果 j 不能在当前区间选数，跳过

    int ip = 1; // 计数器 cnt，初始为 1 是因为包含 j 自己
    int f = 0;  // 临时变量，用于计算当前区间以 j 结尾的新增方案数

    // 枚举前驱学校 k
    for (int k = j - 1; ~k; k--) { // ~k 等价于 k >= 0
        // g[k] 是之前的方案数（值严格小于当前区间）
        // C[ip] 是在当前区间内安排 ip 个学校的方案数
        add(f, 1ll * g[k] * C[ip] % mod);

        // 如果 k 也能在当前区间选数，那么对于更前面的前驱来说，k 就成了中间的可选点，cnt++
        if (l[k] <= i && i + 1 <= r[k])
            ip++;
    }
    // 将当前区间产生的新方案加到 g[j] 中
    add(g[j], f);
}

5. 复杂度分析

• 时间复杂度：
  • 最外层枚举离散化区间：$2N$ 次。
  • 中间层枚举学校 $j$：$N$ 次。
  • 内层枚举前驱 $k$：$N$ 次。
  • 总复杂度：$O(N^3)$。
  • $N=500$，$N^3 \approx 1.25 \times 10^8$，在 1秒 的时限下，由于常数较小且跑不满（ip 计数和区间判断会剪枝），可以通过。
• 空间复杂度：$O(N)$，使用了滚动数组思想，非常优秀。

6. 代码细节注解

#include <bits/stdc++.h>
using namespace std;
const int N = 1010, mod = 1e9 + 7;

// 快读函数
inline int read() { ... }

int n, g[N], C[N], ans;
int l[N], r[N], p[N], inv[N]; // p 是离散化数组，inv 是逆元数组

// 取模加法
void add(int &x, int y) {
    x = x + y >= mod ? x + y - mod : x + y;
}

signed main() {
    n = read();
    // 初始化逆元，用于计算组合数
    inv[1] = g[0] = C[0] = 1; // g[0]=1 代表第0个学校（虚拟）没选，作为初始状态
    for (int i = 2; i <= n; i++)
        inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod;

    // 读入并构建离散化坐标
    for (int i = 1; i <= n; i++) {
        l[i] = read(), r[i] = read() + 1; // 转化为左闭右开 [l, r+1)
        p[++p[0]] = l[i], p[++p[0]] = r[i];
    }

    // 排序去重
    sort(p + 1, p + p[0] + 1), p[0] = unique(p + 1, p + p[0] + 1) - p - 1;

    // 坐标离散化映射
    for (int i = 1; i <= n; i++) {
        l[i] = lower_bound(p + 1, p + p[0] + 1, l[i]) - p;
        r[i] = lower_bound(p + 1, p + p[0] + 1, r[i]) - p;
    }

    // 枚举每一个离散化后的区间
    for (int i = 1; i < p[0]; i++) {
        int len = p[i + 1] - p[i]; // 区间长度

        // 预处理组合数 C(len + x - 1, x)
        for (int j = 1; j <= n; j++)
            C[j] = 1ll * C[j - 1] * (len + j - 1) % mod * inv[j] % mod;

        // DP 更新
        for (int j = n; j; j--) {
            // 剪枝：如果学校 j 的范围不包含当前区间 i，则它不可能作为当前区间的结尾
            if (r[j] < i + 1 || l[j] > i)
                continue;

            int ip = 1, f = 0;
            // 枚举前驱 k
            for (int k = j - 1; ~k; k--) {
                // g[k] 代表以 k 结尾且数值 < 当前区间值的方案数
                // C[ip] 代表在当前区间选数的组合方案
                add(f, 1ll * g[k] * C[ip] % mod);
                
                // 如果 k 也能放在当前区间，则它对于更前面的前驱来说是一个可选的“中间点”
                if (l[k] <= i && i + 1 <= r[k])
                    ip++;
            }
            // 更新 g[j]，累加当前区间贡献的方案
            add(g[j], f);
        }
    }

    // 统计所有以任意学校结尾的方案数
    for (int i = 1; i <= n; i++)
        add(ans, g[i]);

    printf("%d\n", ans);
    return 0;
}

总结

这道题是 数值范围大 + 序列长度小 的典型特征。

1. 离散化解决了数值范围大的问题。
2. 组合数 $\binom{len+cnt-1}{cnt}$ 巧妙地解决了在一个区间内选出若干个数并分配给学校且满足严格递增的问题。
3. $O(N^3)$ DP 实现了状态的转移。