比赛 2026.1.3 评测结果 AWAAWAWAAA
题目名称 极差序列 最终得分 70
用户昵称 梦那边的没好TM 运行时间 0.287 s
代码语言 C++ 内存使用 5.19 MiB
提交时间 2026-01-03 11:59:37
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define cl(a) memset(a,0,sizeof a)
#define ld long double
#define dot(x) fixed<<setprecision(x)
#define foru(a,b,c) for(ll a=b;a<=c;a++)

const ll mod=998245353;
ll n,k,a[200005],pw[200005];

int main(){
    freopen("maxmin.in" ,"r",stdin );
    freopen("maxmin.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin>>n>>k;
    foru(i,1,n)cin>>a[i];
    sort(a+1,a+n+1);
    pw[0]=1;
    foru(i,1,n)pw[i]=pw[i-1]*2%mod;
    ll ans=0;
    if(k==0){
        for(ll i=1;i<=n;){
            ll j=i;
            while(j<=n&&a[j]==a[i])j++;
            ll cnt=j-i;
            ll add=(pw[cnt]-cnt-1)%mod;
            if(add<0)add+=mod;
            ans=(ans+add)%mod;
            i=j;
        }
        cout<<ans;
        return 0;
    }
    ll r=1;
    for(ll l=1;l<=n;){
        ll l2=l;
        while(l2<=n&&a[l2]==a[l])l2++;
        while(r<=n&&a[r]-a[l]<k)r++;
        if(r>n||a[r]-a[l]>k){
            l=l2;
            continue;
        }
        ll r2=r;
        while(r2<=n&&a[r2]==a[r])r2++;
        ll cntL=l2-l;
        ll cntR=r2-r;
        ll mid=r-l2;
        ll ways=(pw[cntL]-1+mod)%mod;
        ways=ways*(pw[cntR]-1+mod)%mod;
        ways=ways*pw[mid]%mod;
        ans=(ans+ways)%mod;
        l=l2;
    }
    cout<<ans;
    return 0;
}