| 比赛 |
2026.1.3 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
极差序列 |
最终得分 |
100 |
| 用户昵称 |
梧叶已同秋雨去 |
运行时间 |
0.329 s |
| 代码语言 |
C++ |
内存使用 |
5.37 MiB |
| 提交时间 |
2026-01-03 11:58:55 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
long long ans;
long long n,k,a[200005],t[200005],mod=998245353;
int main(){
freopen("maxmin.in","r",stdin);
freopen("maxmin.out","w",stdout);
scanf("%lld%lld",&n,&k);t[0]=1;
for(int i=1;i<=n;i++){
t[i]=t[i-1]*2;
t[i]%=mod;
}
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
sort(a+1,a+n+1);
int r=1;
for(int l=1;l<=n;l++){
while(r<=n&&a[r]-a[l]<k) r++;
if(r>n) break;
if(a[r]-a[l]==k){
int cntl=0,cntr=0;
int i=l;
while(i<=n&&a[i]==a[l]){
cntl++;
i++;
}
int j=r;
while(j<=n&&a[j]==a[r]){
cntr++;
j++;
}
long long temp=1;
int mid_cnt=r-i;
temp=temp*t[mid_cnt]%mod;
temp=temp*(t[cntl]-1+mod)%mod;
temp=temp*(t[cntr]-1+mod)%mod;
ans=(ans+temp)%mod;
l=i-1;
}
while(l+1<=n&&a[l+1]==a[l])l++;
}
if(k==0){
ans=0;
for(int i=1;i<=n;i++){
int cnt=1;
while(i+1<=n&&a[i+1]==a[i]){
cnt++;
i++;
}
ans=(ans+t[cnt]-1+mod)%mod;
}
}
printf("%lld",ans);
return 0;
}