力扣每日一题 1621 · 大小为 K 的不重叠线段的数目

每天一题，重点从来不是那句答案，而是从毫无头绪到能自己推的那条路。今天这道 1621（Medium）的正解只有一行组合数 —— 但这一篇不直接抛公式：先圈规则，再手数最小规模，再写暴力，再设计状态，最后让公式自己浮出来。

零、先把题目摊开（复述）

这一节要拿到的东西：把题面翻译成自己的话，并且圈出那三句会决定代码长什么样的规则。

题意用我自己的话说一遍：一维空间里有 n 个点，第 i 个点在坐标 x = i。要选出恰好 k 条线段，每条线段的两个端点都是整数坐标、而且至少跨两个点（左端点 < 右端点）；这 k 条线段之间不重叠。问有多少种选法，答案对 10⁹ + 7 取模。

题面里有三句话必须圈出来，它们决定了后面每一行代码：

• 「每个线段至少覆盖两个点」 —— 所以端点满足 l < r，长度至少 1。
• 「端点可以重合」 —— 不重叠指的是没有公共的内部点，两条线段首尾相接是合法的。这一句是本题最大的坑，也是本题最大的福利。
• 「恰好 k 条」「不需要覆盖全部 n 个点」 —— 所以这是个”选”的问题，不是”分割/覆盖”的问题。

先自己回答这个问题（想好再看，瞄一眼就漏气了）：这题能不能直接当成「从 n 个点里选 2k 个点」来数？　看答案不能。因为每条线段的两个端点是一对（有配对关系），而且相邻线段可以共用端点 —— 直接数 C(n, 2k) 又漏又重。真正的答案要更”松”一点，第五节会推出来。

一、建模：把它画出来

这一节要拿到的东西：一张能让你”看见”题目的图，以及一句话说清”我在数什么”。

遇到”点、线、区间”这类题，第一件事永远是画图。这件事不剧透任何东西，所以直接看：

二、手数最小规模：这是整道题的地基

这一节要拿到的东西：n = 4, k = 2 的全部 5 种方案 —— 它是你以后验任何代码的标尺。

新手最容易跳过的一步，其实是最该做的一步：拿最小的合法输入，把所有方案全部写出来。先拿一张纸自己数，数完再点开下面那条 —— 答案和全部 5 种方案都在里面。

解答5 种方案 + 官方原图（剧透） · 约 2 分钟

5 种分别是：{(0,2),(2,3)}、{(0,1),(1,3)}、{(0,1),(2,3)}、{(1,2),(2,3)}、{(0,1),(1,2)}。

重点观察：其中 4 种都靠”共享端点”才成立，只有 {(0,1),(2,3)} 是完全分开的。如果题目改成”端点不许重合”，答案会从 5 直接掉到 1 —— 一句规则，差 5 倍。

三、第一条路：暴力怎么做到不重不漏

这一节要拿到的东西：一条能写出来的递推规则 + 一个合法的剪枝条件（含一个我写错过的版本）。

很多人写暴力会写成组合枚举（从所有线段里挑 k 条再判重），那样既慢又会重复。更聪明的做法是按位置递推地选：每次选定一条最靠左的线段 (a, b)，下一条线段的左端点必须 ≥ b。先自己想：递归的两个参数是什么？

解答暴力版思路 + 一个真实的踩坑（含图） · 约 2 分钟

递归参数 dfs(start, need)：从坐标 start 开始、还要选 need 条。枚举第一条线段 (a, b)（a ≥ start，b > a），然后递归 dfs(b, need − 1) —— 注意是 b 不是 b+1，因为端点可以重合。

剪枝条件是 n − start < need + 1：因为 need 条线段可以首尾相连，最少只需要 need + 1 个点。这里我第一次写成了 n − start < 2 * need（想当然地按”每条要 2 个点”算），结果 n=3, k=2 直接返回 0 —— 而正确答案是 1。

教训：剪枝写错不会报错，只会静默少算。所以暴力版必须拿”最小规模的全部答案”当标尺。

四、第二条路：设计状态，把”选”变成”递推”

这一节要拿到的东西：一个能回答”最后那个点用不用”的状态定义，以及把整列求和压成一次加法的技巧。

暴力的复杂度是指数级的。要提速，先问自己一句：我到底在重复计算什么？ 答案通常藏在一句话里 —— 前缀、后缀、或者”最后一个点用没用”。状态该怎么定？先想 3 分钟。

解答DP 状态与转移 + 两张表（剧透） · 约 3 分钟

令 f[i][j] = 前 i 个点（0 … i−1）里选 j 条线段的方案数。考虑第 i−1 个点：

① 不用它：方案数 = f[i−1][j]。

② 它是一条线段的右端点：设这条线段是 (m, i−1)，其中 1 ≤ m ≤ i−1；剩下的 j−1 条只能落在前 m+1 个点里（因为可以共用端点 m），即 f[m+1][j−1]。把 m 从 1 到 i−1 加起来。

合起来：f[i][j] = f[i−1][j] + Σ f[m][j−1]，答案就是 f[n][k]。用前缀和把那个 Σ 缓存成 S[i][j]，复杂度从 O(n²k) 降到 O(nk)。

用 n=4, k=2 验一遍：算出来是 5 —— 和第二节手数的一致，这就是好信号。

五、还有第三条路：能不能一行写完？

这一节要拿到的东西：一个闭式公式，以及它的严格来历（这一节是本篇最”值钱”的部分）。

如果你回头看 DP 那张表，会注意到一个巧合：j = 1 那一列是 1, 3, 6, 10 —— 那是 C(i, 2)。这种”表格里冒出组合数”的巧合，通常意味着这题有闭式解。这一节的问题是：能不能不递推，直接”数”出来？

解答公式 C(n+k−1, 2k) 与双射证明（剧透） · 约 3 分钟

第一步：把每条线段 (l, r) 记成两个数 l 和 r − 1，拼成序列 a = (l₁, r₁−1, l₂, r₂−1, …)。因为 l < r 且相邻线段端点可以重合，这个序列满足 a₁ ≤ a₂ < a₃ ≤ a₄ < …：对内有等号，对间严格小于。

第二步：给第 j 个数加上 ⌊j/2⌋，得到 b_j。等号被”撑开”了，b 变成严格递增序列；而它的取值范围是 0 … n+k−2，一共 n+k−1 个位置。

第三步：于是「选 k 条不重叠线段」和「从 n+k−1 个位置里选 2k 个」一一对应 —— 后者就是 C(n+k−1, 2k)。

真例验证：{(0,1),(2,3)} → a = (0, 0, 2, 2) → b = (0, 1, 3, 4)，而 C(5, 4) = 5，正是那 5 种。

六、落地：我的提交代码

下面就是实际提交并通过的那一份（Accepted · 0 ms · 68/68），没有为了文章改过一行。约束是 2 ≤ n ≤ 1000、1 ≤ k ≤ n−1，所以 O(k + log p) 随便跑。

#include <bits/stdc++.h>

class Solution {
    static constexpr long long MOD = 1'000'000'007;

    // 快速幂（费马小定理求逆元）
    static constexpr long long modpow(long long base, long long exp) {
        long long result = 1;
        for (base %= MOD; exp > 0; exp >>= 1) {
            if (exp & 1) result = result * base % MOD;
            base = base * base % MOD;
        }
        return result;
    }

public:
    int numberOfSets(int n, int k) {
        // 结论：方案数 = C(n + k - 1, 2k)
        const long long top = n + k - 1;
        const int bottom = 2 * k;
        if (bottom > top) return 0;

        // C++23：std::ranges::fold_left 对区间做左折叠
        const long long numerator = std::ranges::fold_left(
            std::views::iota(0, bottom), 1LL,
            [top](long long acc, int i) { return acc * ((top - i) % MOD) % MOD; });

        // 分母 = bottom!
        const long long denominator = std::ranges::fold_left(
            std::views::iota(1, bottom + 1), 1LL,
            [](long long acc, int i) { return acc * i % MOD; });

        return static_cast<int>(numerator * modpow(denominator, MOD - 2) % MOD);
    }
};

七、验证：我为什么敢说它是对的

这一节要拿到的东西：一个叫对数器的小习惯 —— 它比任何题解都值钱。

这道题我写了四份实现：暴力 DFS、前缀和 DP、组合公式，以及本机自测用的另一版公式。然后让它们互相对照：对 n ≤ 12 的所有 (n, k) 全跑一遍，四者必须完全一致；再拿官方 5 个示例和边界值兜底。

结果：暴力 × DP × 公式 × 提交版，四方完全一致，ASan/UBSan 也没有任何告警。而在这个过程中，我自己的自测脚本先被这层对照抓出了两个 bug —— 就是前面第三节说的剪枝，以及 DP 前缀和把 f[0][*] 也算进去了（正确的 S 应该从 m = 1 开始）。

八、复盘：今天能带走的东西

迁移卡（剥掉故事壳）：这道题剥掉”点与线段”的外衣，本质是「在一条带等号约束的序列上做计数」 —— 见到”计数 + 相邻可共用边界”的组合，先想双射，再想 DP。同类味道的题以后会收进这个栏目，届时在下面互相链接。

附录 · C++23 小抄（小白版，逐条讲透）

上面那些折叠块是「卡住了才点」；这一节反过来 —— 它不剧透任何东西，所以不折叠。每一条都按同一个套路讲：它是什么 → 为什么有用 → 一段能跑的代码 → 这道题里我用在哪。看完带走的是工具，不是答案。

1. std::ranges::fold_left：把一整个区间「折」成一个数

它是什么：C++23 的新算法。给它一个区间、一个初始值、一条「怎么合并」的规则，它就从左到右一路合并下去，最后返回一个值。

为什么有用：以前要么手写 for 循环（初始值写错、溢出都很难发现），要么用 std::accumulate（只能表达加法语义）。fold_left 能表达任意合并规则，还能配合惰性区间用。

#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> v{1, 2, 3, 4};

    long long sum  = std::ranges::fold_left(v, 0LL, std::plus<>{});       // 1+2+3+4
    long long prod = std::ranges::fold_left(v, 1LL, std::multiplies<>{}); // 1*2*3*4

    std::cout << sum << ' ' << prod << '\n';   // 10 24
}

两个坑：① 累乘的初始值必须是 1LL，写 0 的话结果永远是 0；② 初始值的类型决定返回类型，想避免 int 溢出就写 0LL 而不是 0。

这道题用在哪：分子的连乘、分母的阶乘，各一行。

2. std::views::iota(a, b)：随用随生成的整数区间

它是什么：生成 a, a+1, …, b−1 这一串整数。注意是半开区间，不含 b —— 这是新手最常踩的坑。

为什么有用：它不占内存（用到才生成），却能像容器一样喂给 ranges 算法。写 std::views::iota(0, n) 就等于「从 0 数到 n−1」，不必先造一个 vector。

#include <iostream>
#include <ranges>

int main() {
    for (int i : std::views::iota(0, 5))
        std::cout << i << ' ';        // 0 1 2 3 4（不含 5）
    std::cout << '\n';

    for (int i : std::views::iota(1, 5))
        std::cout << i << ' ';        // 1 2 3 4 —— 阶乘就是它的累乘
}

名字的来历：iota 是希腊字母 ι，来自 APL 语言的整数生成符 ⍳。C++11 就有 std::iota（往容器里填），C++20 才加了惰性版本 std::views::iota。

这道题用在哪：fold_left 的输入就是 std::views::iota(1, bottom + 1) —— 那个 +1 就是为把半开区间补成 1…bottom。

3. 1’000’000’007：写给自己看的数字分隔符

它是什么：C++14 起，数字中间可以插单引号，编译器完全忽略它，纯粹方便人读。

为什么有用：模数 1000000007 有 9 个零，抄题时少写一个零是最冤的 WA。写成 1'000'000'007，一眼就能数清。

int main() {
    long long a = 1'000'000'007;   // 与 1000000007 完全等价
    long long b = 1'000'000'007;
    return a == b ? 0 : 1;         // 返回 0：两者确实相等
}

顺带一句：题面里的「10⁹ + 7」就是这个数，而它是质数 —— 这一点在第 5 条求逆元时会用上。

4. static constexpr 成员函数：能在编译期算的东西

它是什么：constexpr 表示「条件允许时这个函数可以在编译期求值」；static 表示它属于类本身，不用创建对象就能调用。

为什么有用：编译期算完，运行时就不用算；而且把常量与工具函数都收进类里，作用域干净、不容易撞名。

#include <iostream>

class Demo {
    static constexpr long long MOD = 1'000'000'007;      // 编译期常量

    static constexpr long long square(long long x) {      // 编译期可求值
        return x * x % MOD;
    }
public:
    static long long value() { return square(1'000'000'000); }
};

int main() {
    std::cout << Demo::value() << '\n';   // 编译期已算好，运行时零开销
}

陷阱：square 里 x 是 long long，所以 1e9 × 1e9 = 1e18 装得下；要是把参数写成 int，这一行就溢出了（int 上限约 2.1e9）。看到乘法，先问一句：会不会溢出。

5. 组合数取模三件套：分子连乘 → 分母阶乘 → 费马小定理求逆元

要算什么：C(n, r) = n! / (r!(n−r)!) 里有个除法。但在取模的世界里不能直接用 /（整数除法会把余数丢掉）。我们改用乘逆元。

逆元是什么：在模 p（p 为质数）的意义下，a 的逆元是满足 a × x ≡ 1 (mod p) 的那个 x。有了它，a / b 就可以写成 a × inv(b)。

怎么求：费马小定理说 a^(p−1) ≡ 1，两边除以 a 得 a^(p−2) ≡ a⁻¹。于是逆元 = 快速幂求 a^(p−2)。

#include <iostream>

constexpr long long MOD = 1'000'000'007;

// 快速幂：base^exp % MOD，O(log exp)
long long modpow(long long base, long long exp) {
    long long r = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp & 1) r = r * base % MOD;   // 这一位是 1，就乘进去
        base = base * base % MOD;           // 底数平方
        exp >>= 1;                         // 指数右移一位（相当于除以 2）
    }
    return r;
}

// C(n, r) % MOD
long long comb(long long n, long long r) {
    if (r < 0 || r > n) return 0;
    long long num = 1, den = 1;
    for (long long i = 0; i < r; ++i) {
        num = num * ((n - i) % MOD) % MOD;    // 分子：n × (n−1) × … × (n−r+1)
        den = den * (i + 1) % MOD;            // 分母：r!
    }
    return num * modpow(den, MOD - 2) % MOD;  // 乘以分母的逆元，等价于做除法
}

int main() {
    std::cout << comb(5, 4) << '\n';     // 5
    std::cout << comb(36, 14) << '\n';   // 3796297200 % MOD = 796297179（官方示例 3）
}

为什么每一步都要 % MOD：不取模的话，连乘十几项就爆 long long 了。固定写成 a * b % MOD，就不会忘。

这道题用在哪：就是最终提交版本里的那 8 行 —— 分母的逆元一乘，除法就变成了乘法。

6. Lambda 与捕获：把外部变量带进小函数

它是什么：[](参数){ 函数体 } 是匿名函数；方括号里的捕获列表决定它能看见外面哪些变量。

#include <algorithm>
#include <iostream>
#include <ranges>

int main() {
    long long top = 5;

    // [top]：把 top 按值拷进 lambda，函数体里就能用它
    auto mul = [top](long long acc, int i) {
        return acc * ((top - i) % 1000000007) % 1000000007;
    };

    // iota(0,4) 给出 0,1,2,3；累乘 = 5 × 4 × 3 × 2
    std::cout << std::ranges::fold_left(std::views::iota(0, 4), 1LL, mul) << '\n';   // 120
}

三个最常用的写法：[x] 按值拷贝、[&x] 按引用、[&] 全部按引用。陷阱：按值捕获是「快照」，函数体里改它不影响外面；想改外面要写 [&x] 并加 mutable。

7. auto、static_cast 与「溢出」这件小事

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v{1, 2, 3};
    auto n = v.size();                  // auto：类型交给编译器推断（这里是 size_t）
    long long acc = 0;
    for (auto x : v) acc += x;          // 范围 for：不用写下标

    int a = 1'000'000'000;
    // int broken = a * a;              // ← 千万别这样写：溢出，结果不可预测
    long long safe = 1LL * a * a;       // 先转成 long long 再乘，安全

    std::cout << safe << ' ' << n << '\n';
    return static_cast<int>(acc % 1000000007);   // 显式转换：明确告诉读者在缩小类型
}

三条经验：① 能用 auto 就别手写类型名（但要知道推出来的是什么）；② 类型转换一律用 static_cast，不要用 C 风格的括号；③ 做乘法前先看会不会溢出 —— 这道题里每一次连乘后面紧跟 % MOD，就是为了这个。

最后，一张能直接抄进你笔记本的对照表：

明天见。如果你也在刷每日一题，欢迎在评论区贴出你的解法 —— 尤其是和上面两条都不一样的那种。