大小为 K 的不重叠线段的数目

题目

1621. 大小为 K 的不重叠线段的数目

---

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

请你返回 k 个不重叠线段的方案数。由于答案可能很大，请将结果对 10^9 + 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

题解

方法一：

思路

组合数$C_{n+k-1}^{2k}$，在除法时模mod需要求逆元

由于选取k条线段不覆盖，但是相邻线段共用一个端点，处理起来比较麻烦。

如果是选取k条线段不覆盖且相邻线段不能共用一个端点。那么答案就是在n个点里选2k个点的选取方式，即$C_{n}^{2 * k}$。

现在首位可以相接。最多有k-1个相交点，可以增加k-1个节点，问题转化为在n+k-1个节点中选取k条首位不相接线段。为什么可以转化？

令第$i$个根线段的左端为$l_i$，右端为$r_i$

于是有$0 \le l_1<r_1 \le l_2<r_2 \le \cdots \le l_k < r_k < n$

令$l_i’=l_i+(i-1), r_i’=r_i+(i-1)$

此时$0 \le l_1’<r_1’ < l_2’<r_2’ < \cdots < l_k’ < r_k’< n+k-1$。

此时可以用n+k-1中选取2k个数作为答案。

代码

class Solution {
public:
    using ll = long long;
    const ll MOD = 1e9+7;
    ll C(ll n, ll m) { //n个里选m个
        ll inv[n+1];
        inv[1] = 1;
        for (int i=2; i<=n; i++) {
                inv[i] = (MOD-MOD/i)*inv[MOD%i]%MOD;
        }
        ll rt = 1;
        for (int i=m; i>0; i--) {
            rt = rt*(n-i+1)%MOD*inv[i]%MOD;
        }
        return rt;
    }
    int numberOfSets(int n, int k) {
        return C(n+k-1, 2*k);
    }
};

方法二：

思路

定义状态dp[i][j][0]为前i个线放在0…j个点且第i条线右端不在j上。

定义状态dp[i][j][1]为前i个线放在0…j个点且第i条线右端在j上。

状态转移

考虑第i条线段如果右端不在j上，可认为是0…j-1上分配j个点，那么dp[i][j][0] = dp[i][j-1][0]+dp[i][j-1][1]
第i条线段如果右端在j上，有分两种情况讨论：

• 如果第i条线长度是1，那么可认为是0…j-1分配i-1个点，即dp[i-1][j-1][0]+dp[i-1][j-1][1]
• 如果第i条线长度超过1，那么将第i条线从右端长度为1的地方分为两段。仍然可以认为前面0…j-1上分配i条线且右端一定在j-1上。即dp[i][j-1][1]
  所以dp[i][j][1] = dp[i-1][j-1][0]+dp[i-1][j-1][1]+dp[i][j-1][1]

代码

class Solution {
public:
    const long MOD = 1e9+7;
    long dp[1005][1005][2];
    int numberOfSets(int n, int k) {
        dp[0][0][0] = 1;
        for (int i=0; i<=k; i++) {
            for (int j=1; j<n; j++) {
                dp[i][j][0] = dp[i][j-1][0] + dp[i][j-1][1];//第i条线不在j上
                dp[i][j][0] %= MOD;
                dp[i][j][1] = (i>0?dp[i-1][j-1][0] + dp[i-1][j-1][1]:0) + dp[i][j-1][1];
                dp[i][j][1] %= MOD;
            }
        }
        return (dp[k][n-1][0]+dp[k][n-1][1])%MOD;
    }
};