| 比赛 |
2026.1.3 |
评测结果 |
RRRRRRRRRR |
| 题目名称 |
极差序列 |
最终得分 |
0 |
| 用户昵称 |
汐汐很希希 |
运行时间 |
1.322 s |
| 代码语言 |
C++ |
内存使用 |
3.36 MiB |
| 提交时间 |
2026-01-03 09:53:12 |
显示代码纯文本
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10;
const int M=5e5+10;
const int MOD=998245353;
const int MAXX=2147483647;
int n,k,a[N],pres[N],tot=0;
ll po[N],ans=0;
struct Node{
int num,cnt;
}s[N];
int main()
{
freopen("maxmin.in","r",stdin);
freopen("maxmin.out","r",stdin);
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
if(a[i]!=s[tot].num){
tot++;
s[tot].num=a[i];
s[tot].cnt++;
}else s[tot].cnt++;
}
po[0]=1;
for(int i=1;i<=n;i++) po[i]=(po[i-1]*2)%MOD;
if(k==0){
for(int i=1;i<=tot;i++){
int ct=s[i].cnt;
ans=(ans+po[ct]-1+MOD)%MOD;
}
cout<<ans<<'\n';
return 0;
}
for(int i=1;i<=tot;i++) pres[i]=pres[i-1]+s[i].cnt;
/*for(int i=1;i<=tot;i++) cout<<pres[i]<<' ';
cout<<'\n';*/
map<int, int> pa;
for(int i=1;i<=tot;i++) pa[s[i].num]=i;
for(int i=1;i<=tot;i++){
int x=s[i].num,y=s[i].num+k;
if(pa.find(y)==pa.end()) continue;
int j=pa[y];
int cntx=s[i].cnt,cnty=s[j].cnt;
int len=pres[j-1]-pres[i];
ll sol=((po[cntx]-1+MOD)%MOD)*((po[cnty]-1+MOD)%MOD)%MOD;
sol=sol*po[len]%MOD;
ans=(ans+sol)%MOD;
//cout<<i<<' '<<j<<' '<<x<<' '<<y<<' '<<cntx<<' '<<cnty<<' '<<len<<' '<<sol<<'\n';
}
cout<<ans<<endl;
return 0;
}