【算组合数】CF1833 F

灰太狼 2024-03-22 19:48 50阅读 0赞

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

[Problem - F - Codeforces][]

题意：

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

![f23eb74da5e545fdafd29693962204e5.png][]

思路：

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

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

![16ae6b3595854e0190e698d5d3ada1af.jpeg][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using 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; 
    }

[Problem - F - Codeforces]: https://codeforces.com/contest/1833/problem/F
[f23eb74da5e545fdafd29693962204e5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/9fd3411d0cc848ecb867cf05570df153.png
[16ae6b3595854e0190e698d5d3ada1af.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/d43969c4c96f438fb42105997e7044ef.png