文化传播公司网站模版,做美食类网站分析,舒城县住房和城乡建设局网站,wordpress js错误少见地秒了这道1700#xff0c;要是以后都这样就好了....
Problem - F - Codeforces
题意#xff1a;
给定一个数列#xff0c;让你在这个数列里找一个大小为M的子集#xff0c;使得极差不超过M 思路#xff1a;
子集#xff0c;不是子序列#xff0c;说明和顺序无…少见地秒了这道1700要是以后都这样就好了....
Problem - F - Codeforces
题意
给定一个数列让你在这个数列里找一个大小为M的子集使得极差不超过M 思路
子集不是子序列说明和顺序无关因此可以考虑排序
观察一下样例可知排序后我们可以双指针一下然后方案数就是区间map之积 Code
#include bits/stdc.h#define int long longusing namespace std;const int mxn2e510;
const int mxe2e510;
const int mod1e97;mapint,int mp;int N,M;
int len0;
int a[mxn],b[mxn],c[mxn],pre[mxn];int ksm(int a,int b,int mod){int res1ll;while(b){if(b1) res(res*a)%mod;a(a*a)%mod;b1;}return res;
}
void solve(){mp.clear();len0;cinNM;setint S;for(int i1;iN;i){cina[i];S.insert(a[i]);mp[a[i]];}for(auto it:S) b[len]it; for(int i1;ilen;i) c[i]mp[b[i]];pre[0]1;for(int i1;ilen;i) pre[i]pre[i-1]*c[i]%mod;int r1;int ans0;for(int l1;llen;l){while(rlenb[r]-b[l]Mr-l1M) r;if(r-1-l1Mb[r-1]-b[l]M) anspre[r-1]*ksm(pre[l-1],mod-2,mod)%mod;}coutans%mod\n;
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __1;cin__;while(__--)solve();return 0;
}
