| 比赛 |
2026.1.3 |
评测结果 |
AWAAWAWAAA |
| 题目名称 |
极差序列 |
最终得分 |
70 |
| 用户昵称 |
彭欣越 |
运行时间 |
0.962 s |
| 代码语言 |
C++ |
内存使用 |
13.28 MiB |
| 提交时间 |
2026-01-03 09:37:13 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200010,inf=1e9+10,mod=998245353;
int n,m,k,a[N],b[N],t[N],s[N];
ll ans;
map<ll,int>mp;
int get (int x) {
return lower_bound(b+1,b+1+m,x)-b;
}
ll qpow (ll x,int k) {
ll sum=1;
//cout << k <<endl;
while (k) {
if (k%2==1) {
sum*=x;
sum%=mod;
}
x*=x;
x%=mod;
k>>=1;
}
//cout << sum <<endl;
return sum;
}
int main () {
freopen("maxmin.in","r",stdin);
freopen("maxmin.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin >> n >> k;
for (int i=1;i<=n;i++) {
cin >> a[i];
//cout << i <<endl;
b[i]=a[i];
}
sort(b+1,b+1+n);
m=unique(b+1,b+1+n)-b-1;
for (int i=1;i<=n;i++) {
//cout << get(a[i]) <<endl;
t[get(a[i])]++;
}
for (int i=1;i<=n;i++) s[i]=s[i-1]+t[i];
for (int i=1;i<=m;i++) {
//cout << b[i] <<endl;
if (mp[b[i]]) {
//cout << s[get(mp[b[i]])] <<' '<< s[get(b[i])-1] <<endl;
ans=(ans+(qpow(2,t[get(mp[b[i]])])-1)*(qpow(2,t[i])-1)%mod*qpow(2,s[get(b[i])-1]-s[get(mp[b[i]])])%mod)%mod;
}
if (b[i]+k<=inf) mp[b[i]+k]=b[i];
}
cout << ans <<endl;
return 0;
}