本文共 1454 字，大约阅读时间需要 4 分钟。

本题为hard版，还有一个easy版，区别在于k和m的取值不同。

题意：

给出一个由n个数字组成的数组 \(a\)。现在定义一种子集为\(\{A_1, A_2, A_3, ..., A_m\}\)，使得这个子集中的最大值和最小值的差值不超过k，其中m和k是给出的。现在问你这种子集有几个。

思路：

对给出的数组进行排序，用\(for\)循环枚举子集中的\(A_1\)，之后用upper_bound找到数组中第一个数字，使得这个数字减去\(A_1\)大于k。若这个数字和\(A_1\)之间元素的个数大于\(m - 1\)，那么利用组合数\(C_n^m\)就可以求出部分答案。最后将每一部分的答案加起来就可以得到最终答案。

额外知识：

由于题目要求取模，但是组合数中却有除法，不能直接取模，所以需要用到逆元。

AC代码（直接用板子）：

#include 
   
    #include 
    
     #include 
     
      const int N = 2e5 + 5;const int mod = 1e9 + 7;typedef long long ll;ll f[N];ll qpow(ll a, ll b) {    ll ans = 1, base = a;    while (b) {        if (b & 1) ans = ans * base % mod;        base = base * base % mod;        b >>= 1;    }    return ans;}void init() {    f[0] = 1;    for (int i = 1; i <= 2e5; i++) {        f[i] = f[i - 1] * i % mod;    }}ll cal(ll n, ll m) {    if (n < m) return 0;    return 1ll * f[n] * qpow(f[m], mod - 2) % mod * qpow(f[n - m], mod - 2) % mod;}int a[N];int main () {    init();    int T, n, m, k;    scanf ("%d", &T);    while (T--) {        scanf ("%d %d %d", &n, &m, &k);        for (int i = 0; i < n; i++) {            scanf ("%d", &a[i]);        }        std::sort (a, a + n);        int p = 0;        ll ans = 0;        for (int i = 0; i < n; i++) {            p = (int)(std::upper_bound(a, a + n, a[i] + k) - a);            if (p - i >= m) {                ans = ans + cal(p - i - 1, m - 1);                ans = ans % mod;            }        }        printf ("%lld\n", ans);    }    return 0;}