比赛 2026.1.3 评测结果 RRRRRRRRRR
题目名称 极差序列 最终得分 0
用户昵称 汐汐很希希 运行时间 1.322 s
代码语言 C++ 内存使用 3.36 MiB
提交时间 2026-01-03 09:53:12
显示代码纯文本
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10;
const int M=5e5+10;
const int MOD=998245353;
const int MAXX=2147483647;
int n,k,a[N],pres[N],tot=0;
ll po[N],ans=0;
struct Node{
	int num,cnt;
}s[N];
int main()
{
	freopen("maxmin.in","r",stdin);
    freopen("maxmin.out","r",stdin);
    
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
	for(int i=1;i<=n;i++){
    	if(a[i]!=s[tot].num){
    		tot++;
    		s[tot].num=a[i];
	    	s[tot].cnt++;
		}else s[tot].cnt++;
	}
    po[0]=1;
    for(int i=1;i<=n;i++) po[i]=(po[i-1]*2)%MOD;
    if(k==0){
        for(int i=1;i<=tot;i++){
            int ct=s[i].cnt;
            ans=(ans+po[ct]-1+MOD)%MOD;
        }
        cout<<ans<<'\n';
        return 0;
    }
    for(int i=1;i<=tot;i++) pres[i]=pres[i-1]+s[i].cnt;
    /*for(int i=1;i<=tot;i++) cout<<pres[i]<<' ';
	cout<<'\n';*/
    map<int, int> pa;
    for(int i=1;i<=tot;i++) pa[s[i].num]=i;
    for(int i=1;i<=tot;i++){
    	int x=s[i].num,y=s[i].num+k;
    	if(pa.find(y)==pa.end()) continue;
        int j=pa[y];
        int cntx=s[i].cnt,cnty=s[j].cnt;
        int len=pres[j-1]-pres[i];
        ll sol=((po[cntx]-1+MOD)%MOD)*((po[cnty]-1+MOD)%MOD)%MOD;
        sol=sol*po[len]%MOD;
        ans=(ans+sol)%MOD;
        //cout<<i<<' '<<j<<' '<<x<<' '<<y<<' '<<cntx<<' '<<cnty<<' '<<len<<' '<<sol<<'\n'; 
	}
	cout<<ans<<endl;
    return 0;
}