【算组合数】CF1833 F

少见地秒了这道1700，要是以后都这样就好了.... 

Problem - F - Codeforces

题意：

给定一个数列，让你在这个数列里找一个大小为M的子集，使得极差不超过M

 

思路：

子集，不是子序列，说明和顺序无关，因此可以考虑排序

观察一下样例可知，排序后我们可以双指针一下，然后方案数就是区间map之积

 

Code：

#include <bits/stdc++.h>#define int long longusing namespace std;const int mxn=2e5+10;
const int mxe=2e5+10;
const int mod=1e9+7;map<int,int> mp;int N,M;
int len=0;
int a[mxn],b[mxn],c[mxn],pre[mxn];int ksm(int a,int b,int mod){int res=1ll;while(b){if(b&1) res=(res*a)%mod;a=(a*a)%mod;b>>=1;}return res;
}
void solve(){mp.clear();len=0;cin>>N>>M;set<int> S;for(int i=1;i<=N;i++){cin>>a[i];S.insert(a[i]);mp[a[i]]++;}for(auto it:S) b[++len]=it; for(int i=1;i<=len;i++) c[i]=mp[b[i]];pre[0]=1;for(int i=1;i<=len;i++) pre[i]=pre[i-1]*c[i]%mod;int r=1;int ans=0;for(int l=1;l<=len;l++){while(r<=len&&b[r]-b[l]<M&&r-l+1<=M) r++;if(r-1-l+1==M&&b[r-1]-b[l]<M) ans+=pre[r-1]*ksm(pre[l-1],mod-2,mod)%mod;}cout<<ans%mod<<'\n';
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;cin>>__;while(__--)solve();return 0; 
}