比赛 2026.1.3 评测结果 WWAAWAWAAA
题目名称 极差序列 最终得分 60
用户昵称 梦那边的美好CE 运行时间 0.277 s
代码语言 C++ 内存使用 5.97 MiB
提交时间 2026-01-03 09:36:31
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
#define N 514514
#define mod 998245353
using namespace std;

inline void read(int &x) {bool neg = false;x = 0;char ch = 0;while (ch < '0' || ch > '9') {if (ch == '-') neg = true;ch = getchar();}if (neg) {while (ch >= '0' && ch <= '9') {x = x * 10 + ('0' - ch);ch = getchar();}} else {while (ch >= '0' && ch <= '9') {x = x * 10 + (ch - '0');ch = getchar();}}return;}

template <typename T> inline void write(T x) {if (x < 0) x = -x, putchar('-');if (x > 9) write(x / 10);putchar(x % 10 + 48);}

int C2(int n){//C_n^2
	return n*(n-1)/2;
}

int n,k,a[N],f2[N],pre2[N];

signed main(){
	freopen("maxmin.in","r",stdin);freopen("maxmin.out","w",stdout);
	read(n);read(k);
	for(int i=1;i<=n;i++)read(a[i]);

	f2[0]=pre2[0]=1;f2[1]=2;pre2[1]=3;
	for(int i=2;i<=n;i++){
		f2[i]=f2[i-1]*2;f2[i]%=mod;
		pre2[i]=pre2[i-1]+f2[i];pre2[i]%=mod;
	}
	
	// for(int i=1;i<=n;i++){
	// 	write(f2[i]);putchar(' ');
	// }putchar('\n');
	// for(int i=1;i<=n;i++){
	// 	write(pre2[i]);putchar(' ');
	// }

	sort(a+1,a+n+1);

	if(k==0){
		int len=1,ans=0;
		for(int i=2;i<=n+1;i++){
			if(a[i-1]==a[i])len++;
			else{
				if(len>=2){
					for(int j=0;j<=len-2;j++){
						ans+=pre2[j];
						ans%=mod;
					}
				}
				len=1;
			}
		}
		write(ans);
		return 0;
	}

	int i=1,j=2,ans=0;
	while(j<=n){
		if(i==j)j++;
		if(j>n)break;
		if(a[j]-a[i]<k){
			j++;
		}else if(a[j]-a[i]>k){
			i++;
		}else{
			ans+=f2[j-i-1];
			ans%=mod;
			j++;
		}
	}
	write(ans);
	return 0;
}