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