题意：有n个数，让我们求出有多少个 个数 恰好为m的集合，并且最大值最小值相差小于等于k的集合个数

思路：对原本的数组进行排序，然后从1到n暴力枚举一遍即可；

　　　在暴力枚举的时候，规定当前位置的数字必须在集合当中（能够防止重复计算）；

　　　另外，这道题在计算的时候，需要用到组合数和逆元的知识点

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn=2e5+10;
 5 const int mod=1e9+7;
 6 ll base[maxn];
 7 ll a[maxn];
 8 int n,m,k;
 9 void init()
10 {
11     base[1]=1;
12     base[0]=1;
13     for(int i=2;i<=maxn-10;i++){
14         base[i]=base[i-1]*i%mod;
15     }
16 }
17 void ex_gcd(ll a, ll b, ll &x, ll &y, ll &d){
18     if (!b) {d = a, x = 1, y = 0;}
19     else{
20         ex_gcd(b, a % b, y, x, d);
21         y -= x * (a / b);
22     }
23 }
24 ll inv(ll t, ll p){//如果不存在，返回-1
25     ll d, x, y;
26     ex_gcd(t, p, x, y, d);
27     return d == 1 ? (x % p + p) % p : -1;
28 }
29 ll cal(ll x,ll y)
30 {
31     return base[x]*inv(base[x-y],mod)%mod*inv(base[y],mod)%mod;
32 }
33 int main()
34 {
35     init();
36     int T;
37     scanf("%d",&T);
38     while(T--){
39         scanf("%d%d%d",&n,&m,&k);
40         for(int i=1;i<=n;i++){
41             scanf("%lld",&a[i]);
42         }
43         sort(a+1,a+1+n);
44         ll ans=0;
45         for(int i=1;i<=n;i++){
46             int l=upper_bound(a+1,a+1+n,a[i]+k)-a;
47             int len=l-i;
48             if(len<m) continue;
49             ans+=cal(len-1,m-1);
50             ans%=mod;
51         }
52         printf("%lld\n",ans);
53     }
54     return 0;
55 }

View Code