F. Ira and Flamenco

题目链接：Problem - F - Codeforces

题目大意：给n,m n个数让从中选m个数满足一下条件：

1.m个数互不相同

2.里面的任意两个数相减的绝对值不能超过m

求这n个数有多少组数据满足。

第一行包含一个整数 t ( 1 ≤ t ≤ 1e4 ) - 测试用例数。

每个测试用例的第一行包含整数 n 和 m ( 1≤ m ≤ n ≤ 2⋅1e5 ) 

每个测试用例的第二行包含 n 个整数 a1,a2,…,an ( 1≤ ai ≤ 1e9 ) 。

保证所有测试用例的 n 之和不超过 2⋅1e5。

用到的知识：滑动窗口， 乘法原理，  乘法逆元

解题思路：首先通过选择m个数， 要不同，两两组合不能相减绝对值不可以超过m, 即里面的最大值与最小值之差不可以超过m, 所以可以采用滑动窗口实现， 窗口大小m.

组合数学的运用， 当有重复的数出现， 那么就会用到乘法原理， 列如 m==2,对于数列 1 2 2 3 4 对于 数列1 2 时， 2可以有两种选择， 所以再该窗口时， 应要乘以二。 

 而对于当窗口滑动时，滑出窗口的数的个数要被除下来， 由于题目要求ans要取模1e9+7, 所以用到乘法逆元，即可以实现整个窗口的滑动。MOD = 1e9+7, 可以使用费马小定理求出逆元。

为了选择去重与排序，采用map收集。

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;
using i128 = __int128;

const int MOD = 1e9+7;
i64 ksm(i64 a, i64 b){
    i64 res = 1;
    while(b) {
        if(b&1) {
            res = res * a % MOD;
        }
        b>>=1;
        a  = a * a % MOD;
    }
    return res;
}
void solve(){
    int n, m;
    cin >> n >> m;
    vector<int> a(1);
    i64 ans = 0;
    map<int,i64> mp;
    for(int i=0; i<n; i++) {
        int t;
        cin >> t;
        mp[t] ++;
    }
    for(auto& [x,y] : mp) {
        a.push_back(x);//去重
    }
    sort(a.begin(), a.end());
    int i=1, j=1;
    int sz = a.size();
    i64 cnt = 1;
    while(i<sz) {
        while(j<sz && a[j] < a[i]+m) {//滑动窗口
            cnt = (cnt * mp[a[j]]) % MOD;
            j++;
        }
        if(j-i==m) { //更新ans
            ans = (ans+cnt + MOD) %MOD;
        }
        //滑出窗口，乘以a[i]数的逆元即可以除以该数
        cnt  = (cnt*ksm(mp[a[i]], MOD-2) + MOD) % MOD;//费马小定理求逆元
        i++;
    }
    cout << ans << "\n";
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t--) {
        solve();
    }
}

  感谢各位的收看与点赞， 欢迎大佬指正。