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