解题思路

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

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

题面描述

给定三个整数 $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]$。