1621.大小为 K 的不重叠线段的数目：组合数学(快速幂+模逆元)

【LetMeFly】1621.大小为 K 的不重叠线段的数目：组合数学(快速幂+模逆元)

力扣题目链接：https://leetcode.cn/problems/number-of-sets-of-k-non-overlapping-line-segments/

给你一维空间的 n 个点，其中第 i 个点（编号从 0 到 n-1）位于 x = i 处，请你找到 恰好 k 个不重叠 线段且每个线段至少覆盖两个点的方案数。线段的两个端点必须都是 整数坐标 。这 k 个线段不需要全部覆盖全部 n 个点，且它们的端点 可以 重合。

请你返回 k 个不重叠线段的方案数。由于答案可能很大，请将结果对 109 + 7 取余 后返回。

 

示例 1：

输入：n = 4, k = 2
输出：5
解释：
如图所示，两个线段分别用红色和蓝色标出。
上图展示了 5 种不同的方案 {(0,2),(2,3)}，{(0,1),(1,3)}，{(0,1),(2,3)}，{(1,2),(2,3)}，{(0,1),(1,2)} 。

示例 2：

输入：n = 3, k = 1
输出：3
解释：总共有 3 种不同的方案 {(0,1)}, {(0,2)}, {(1,2)} 。

示例 3：

输入：n = 30, k = 7
输出：796297179
解释：画 7 条线段的总方案数为 3796297200 种。将这个数对 109 + 7 取余得到 796297179 。

示例 4：

输入：n = 5, k = 3
输出：7

示例 5：

输入：n = 3, k = 2
输出：1

 

提示：

• 2 <= n <= 1000
• 1 <= k <= n-1

解题方法：组合数学

咱们站在资源分配的视角。

$n$个点共有$n-1$个长度可以分配，其中$k$个线段占据了$k$个长度，剩下的$n-1-k$个长度怎么分？

1. 可以分配到任何一个线段上（共有$k$个线段）
2. 可以分配到任何线段两边的空白位置上（共有$k+1$个空白位置）

问题变成了把$n-1-k$个东西放到$2k+1$个位置，有多少种放法。

把$a$个东西放到$b$个位置有多少种方法呢？相当于$a$个东西中间插入$b-1$个隔板，相当于东西加隔板共$a+b-1$个位置，其中选$b-1$个作为隔板，即$C_{a+b-1}^{b-1}$。

也就是说，本题的$C_{n+k-1}^{2k}$即为答案。

现在还有一个问题就是在大数对质数取模的情况下，怎么计算组合数$C_a^b$。

$$C_a^b = \frac{a!}{(a-b)!b!} = a! \times ((a-b)!)^{-1} \times (b!)^{-1}$$

而模运算下，$a^-1 \equiv a^{MOD-2} \mod MOD$，所以我们可以用快速幂来计算模逆元。

预处理优化

由于本题数据量$n$和$k$都是$10^3$量级，所以我们可以预处理出$0\sim 2000$范围内每个数的阶乘和模逆元。

阶乘$Jie[i]=Jie[i-1] \times i$，我们可以从$Jie[0]=1$开始处理到$Jie[2000]$。

而$2000!$的模逆元 $Rev[2000] = (2000!)^{-1} \equiv (2000!)^{MOD-2} \mod MOD$，前面计算出$2000!$的结果$Jie[2000]$后，可以用快速幂在$\log MOD$的时间内计算出$Rev[2000]$。

由于$Rev[i]=Jie[i]^{-1}=(Jie[i-1] \times i)^{-1}=Rev[i-1] \times i^{-1}$，所以$Rev[i-1] = Rev[i] \times i$，我们可以从$Rev[2000]$开始倒序处理到$Rev[0]$。

时空复杂度分析

• 时间复杂度：预处理$O(n+k)$，单次运行$O(1)$
• 空间复杂度：总计$O(n+k)$，单次运行额外空间复杂度$O(1)$

AC代码

C++

/*
 * @LastEditTime: 2026-09-17 08:33:08
 */
typedef long long ll;
const ll MOD = 1e9 + 7;
ll Jie[2001];
ll Rev[2001];

ll myPow(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1) {
            ans = ans * a % MOD;
        }
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}

// J[i] = J[i-1] * i
// R[i] = (J[i-1] * i)^-1 = J[i-1]^-1 * i^-1 = R[i-1] * i^-1
// R[i-1] = R[i] * i
int _ = []{
    Jie[0] = 1;
    for (int i = 1; i <= 2000; i++) {
        Jie[i] = Jie[i - 1] * i % MOD;
    }
    Rev[2000] = myPow(Jie[2000], MOD - 2);
    for (int i = 2000; i; i--) {
        Rev[i - 1] = Rev[i] * i % MOD;
    }
    return 0;
} ();


class Solution {
private:
    int C(ll a, ll b) {
        return (Jie[a] * Rev[a - b] % MOD) * Rev[b] % MOD;
    }
public:
    int numberOfSets(int n, int k) {
        // 长n-1，k条线，还有n-1-k长度可供使用
        // 这些长度可以放到k条线段上，也可以放到k条线段两边的k+1个空白位置
        // 问题变成了把n-1-k个东西放到2k+1个位置
        //
        // a个东西放b个位置有多少种方法？相当于a个东西插入b-1个隔板
        // 相当于a+b-1个位置其中选b-1个作为隔板，即C_{a+b-1}^{b-1}
        // 回到本题则是C_{n+k-1}^{2k}
        //
        // C_a^b = a(a-1)(a-2)...(a-b+1) / b(b-1)(b-2)...1
        //       = a/1 * (a-1)/2 * (a-2)/3 * ... * (a-b+1)/b
        // a/t相当于a*rev(t)相当于a*t^{MOD-2}
        //
        // 换种思路，C_a^b= a! / (a-b)!b!
        return C(n + k - 1, 2 * k);
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源