Description
给出一个由 (n) 个数字组成的数组。现在定义一种子集为 ({A_1, A_2, A_3, ..., A_m}) 使得这个子集中的最大值和最小值的差值不超过 (k),其中 (m) 和 (k) 是给出的。现在问你这种子集有几个。
Solution
最初的想法是将每个数的重数统计出来,然后枚举最大的数以及最大数选多少个,剩下的用组合数计算。
更简单的方法是,直接排序,然后枚举最大数的位置,利用前缀和统计这个数前面有多少个不小于它 (-k) 的数,然后用组合数计算即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
const int N = 1e6 + 5;
int fac[N], ifac[N];
int qpow(int p, int q)
{
return (q & 1 ? p : 1) * (q ? qpow(p * p % mod, q / 2) : 1) % mod;
}
int inv(int p)
{
return qpow(p, mod - 2);
}
void presolve()
{
fac[0] = 1;
for (int i = 1; i < N; i++)
fac[i] = fac[i - 1] * i % mod;
ifac[N - 1] = inv(fac[N - 1]);
for (int i = N - 2; i >= 0; i--)
ifac[i] = ifac[i + 1] * (i + 1) % mod;
}
int ncr(int n, int m)
{
if (n < m)
return 0;
return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
signed main()
{
ios::sync_with_stdio(false);
int t;
cin >> t;
presolve();
while (t--)
{
int n, m, k;
cin >> n >> m >> k;
vector<int> a(n + 2);
vector<int> c(n + n + 2);
for (int i = 1; i <= n; i++)
cin >> a[i], c[a[i]]++;
for (int i = 1; i <= n; i++)
c[i] += c[i - 1];
sort(&a[1], &a[n + 1]);
int ans = 0;
for (int i = 1; i <= n; i++)
{
int cnt = i -1;
if (a[i] - k - 1 > 0)
cnt -= c[a[i] - k - 1];
ans += ncr(cnt, m - 1);
ans %= mod;
}
cout << ans << endl;
}
}