codeforce每日一题链接
题目链接
题目描述
给定一个长度为n的数组,在给定m,请你找出数组中的所有满足下要求的子序列数量。
要求:子序列长度为m,子序列中最大值与最小值之差不超过m,子序列中数字;两两不同。
样例
输入样例1
9
7 4
8 10 10 9 6 11 7
5 3
4 2 2 3 6
8 2
1 5 2 2 3 1 3 3
3 3
3 3 3
5 1
3 4 3 10 7
12 3
5 2 1 1 4 3 5 5 5 2 7 5
1 1
1
3 2
1 2 3
2 2
1 2
输出样例1
5
2
10
0
5
11
1
2
1
算法1
(滑动窗口) $O(n)$
子序列长度为m,又两两不同,最大差值还得不超过m,那就是差值只能是m-1,也就是子序列中数字是连续m个数字,那么我们只需要将数组排个序,用滑动窗口就行。别忘了将除法转成乘法,逆元。
C++ 代码
// https://www.acwing.com/blog/content/34755/
#include<bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;
const int N = 2e5 + 10, M = N * 2, INF = 0x3f3f3f3f, mod = 1e9+7;
int n, m;
LL w[N];
inline LL qmi(LL a, LL k, LL p)
{
LL res=1;
while(k)
{
if(k&1) res=res*a%p;
k>>=1;
a=a*a%p;
}
return res;
}
inline void solve()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>w[i];
map<LL,LL> ma;
for(int i=1;i<=n;i++) ma[w[i]]++;
sort(w+1, w+n+1);
int cnt = unique(w+1,w+n+1) - w - 1;
LL res = 0, tmp = 1;
w[0] = w[1] - 1;
LL l = 0;
for(int i=1;i<=cnt;i++){
if(w[i]==w[i-1]+1){
l++;
tmp=tmp*ma[w[i]]%mod;
if(i>m && l>m) tmp=tmp*qmi(ma[w[i-m]],mod-2,mod)%mod;
}else tmp = ma[w[i]], l = 1;
if(i>=m && l>=m) res = (res + tmp) % mod;
}
cout<<res<<endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin>>T;
while(T--)
{
solve();
}
return 0;
}