解题思路

我们要从序列 $[1,n]$ 中选出 $k$ 个严格递增的下标 $(x_1<\cdots<x_k)$，并满足相邻差 $\ge L$。

关键等价变换（抽空法 / 间隔消元）： 对每个被选下标“挤掉”它之前必须预留的 $(L-1)$ 个空位：

则有

且相邻差条件自动变成“严格递增”即可。于是原问题转化为：从 $[1,m]$ 中任选 $k$ 个数，答案就是组合数

特殊情况：当 $L=1$ 时，$m=n$，即为普通的“从 $n$ 里选 $k$”——答案 $\binom{n}{k}$。

划分型动态规划实现组合数： 用经典的“选/不选”划分思路计算 $\binom{m}{k}$：

• 状态定义：$dp[i][j]$ 表示从 $[1,i]$ 中选 $j$ 个的方案数。

• 状态转移：

  $$dp[i][j] = dp[i-1][j] + dp[i-1][j-1]$$

  （第 $i$ 个元素不选/选）

• 边界：$dp[i][0]=1$；当 $j>i$ 时为 $0$。

由于本题数据小（$n\le 60$），用 64 位整数即可承载结果（$\binom{60}{30}\approx 1.18\times 10^{17}$）。

代码实现

Python

# 题面功能封装在外部函数中
def count_ways(n: int, k: int, L: int) -> int:
    # k=0：不选任何元素，方案数为1
    if k == 0:
        return 1
    # 计算等价问题的上界 m
    m = n - (L - 1) * (k - 1)
    # 不可行：可选范围不足
    if m < k or m < 0:
        return 0

    # 划分型DP计算 C(m, k)
    dp = [[0] * (k + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = 1  # 选0个的方案始终为1
        # 只需计算到 min(i, k)
        up = min(i, k)
        for j in range(1, up + 1):
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]
    return dp[m][k]

if __name__ == "__main__":
    import sys
    data = sys.stdin.read().strip().split()
    n, k, L = map(int, data)
    print(count_ways(n, k, L))

Java

import java.util.*;

// ACM 风格，主类名为 Main
public class Main {

    // 题面功能封装在外部函数中
    static long countWays(int n, int k, int L) {
        if (k == 0) return 1L; // 不选任何元素
        long m = (long)n - (long)(L - 1) * (long)(k - 1);
        if (m < k || m < 0) return 0L; // 不可行

        // 划分型DP计算 C(m, k)
        int M = (int)m;
        long[][] dp = new long[M + 1][k + 1];
        for (int i = 0; i <= M; i++) {
            dp[i][0] = 1L; // 选0个
            int up = Math.min(i, k);
            for (int j = 1; j <= up; j++) {
                // 组合数递推：不选i 或 选i
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
            }
        }
        return dp[M][k];
    }

    public static void main(String[] args) {
        // 数据范围很小，Scanner 足够
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int L = sc.nextInt();
        System.out.println(countWays(n, k, L));
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

// 题面功能封装在外部函数中
unsigned long long countWays(long long n, long long k, long long L) {
    if (k == 0) return 1ULL; // 不选任何元素
    long long m = n - (L - 1) * (k - 1);
    if (m < k || m < 0) return 0ULL; // 不可行

    // 划分型DP计算 C(m, k)
    int M = (int)m;
    int K = (int)k;
    vector<vector<unsigned long long>> dp(M + 1, vector<unsigned long long>(K + 1, 0ULL));
    for (int i = 0; i <= M; ++i) {
        dp[i][0] = 1ULL; // 选0个
        int up = min(i, K);
        for (int j = 1; j <= up; ++j) {
            // 组合数递推：不选i 或 选i
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
        }
    }
    return dp[M][K];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n, k, L;
    if (!(cin >> n >> k >> L)) return 0;
    cout << countWays(n, k, L) << "\n";
    return 0;
}

题面描述

给定三个整数 $n,k,L$。从序列 $\{1,2,\ldots,n\}$ 中选择 $k$ 个不同的下标 $1\le x_1<x_2<\cdots<x_k\le n$，并满足相邻下标的差都至少为 $L$，即 $x_{i+1}-x_i\ge L$（对所有 $1\le i<k$）。 求满足条件的方案数。

输入输出

输入： 一行三个整数 $n,k,L$。

输出： 一行输出一个整数，表示满足条件的方案数。

数据范围

• $1 \le n \le 60$
• $0 \le k \le n$
• $1 \le L \le n$

样例

输入

3 2 1

输出

3

说明 从 $[1,2,3]$ 中选 2 个且相邻下标差至少 1，方案为 $[1,2],[1,3],[2,3]$。

输入

5 3 2

输出

1

说明 相邻下标差至少为 2，只能选 $[1,3,5]$。