比赛 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;
}