题解
知识点：组合数学，枚举，双指针。
注意到，长度为 \(m\) 且数字各不相同的子序列，那么最大值与最小值的差至少为 \(m-1\) 。因此，对于任意子序列，它是合法的，当且仅当，将其从小到大排序后是以 \(1\) 为等差的数列。
因此，我们可以直接从原数组处理出所有不同数字的个数，并对数字从小到大排序后作为新的数组。在新数组上滑动窗口枚举长度为 \(m\) 的区间，我们检验是否满足最大值减最小值小于 \(m\) 即可。
一个合法的区间的贡献显然为所有数字个数的乘积，我们可以枚举区间时一并处理。
时间复杂度 \(O(n(\log n + \log P))\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int P = 1e9 + 7;
int qpow(int a, ll k) {
int ans = 1;
while (k) {
if (k & 1) ans = 1LL * a * ans % P;
k >>= 1;
a = 1LL * a * a % P;
}
return ans;
}
int a[200007];
bool solve() {
int n, m;
cin >> n >> m;
for (int i = 1;i <= n;i++) cin >> a[i];
sort(a + 1, a + n + 1);
vector<pair<int, int>> cnt = { {},{a[1],1} };
for (int i = 2;i <= n;i++) {
if (a[i] == a[i - 1]) cnt.back().second++;
else cnt.push_back({ a[i],1 });
}
int len = cnt.size() - 1;
if (len < m) {
cout << 0 << '\n';
return true;
}
int mul = 1;
for (int i = 1;i <= m;i++) mul = 1LL * mul * cnt[i].second % P;
int ans = 0;
if (cnt[m].first - cnt[1].first < m) ans = mul;
for (int i = m + 1;i <= len;i++) {
mul = 1LL * mul * cnt[i].second % P;
mul = 1LL * mul * qpow(cnt[i - m].second, P - 2) % P;
if (cnt[i].first - cnt[i - m + 1].first < m) (ans += mul) %= P;
}
cout << ans << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}