526互联

Educational Codeforces Round 118

发布时间 2023-08-28 21:49:54作者: gan_coder

好烦，又是只有三题，讲课的老师实在是太吵了，没法思考细节

A题开始还搞麻烦了
B题纯诈骗，找最小的做y即可
C题直接二分判断即可
D题其实没看多久我就秒了，
对于当前的数x来说无非就是
mex=x-1
mex=x
mex=x+1

\(f[x]\)表示mex=x，后面没有数
\(g[x]\)表示mex=x，后面有x+1，并且只可能是x+1，不可能更大

转移一下即可

被吵到没心态了，不过也从另一方面说明我抗压能力不行，之前在家环境比较轻松，也可以随意走动，也比较随意，思维就比较放松，基本都能写完D，抗干扰能力还要提升。

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<set>
#include<queue>
#include<cmath>
#include<unordered_map>
#include<map>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define A puts("YES")
#define B puts("NO")

using namespace std;
typedef double db;
typedef long long ll;
const ll mo=998244353;
const int N=5e5+5;
ll f[N],g[N],n,a[N],x,ans;
void add(ll &x,ll y){
	x=(x+y)%mo;
}
int main() {
	
//	freopen("data.in","r",stdin);
	int T;
	scanf("%d",&T);
	while (T--){
		scanf("%lld",&n);
		fo(i,1,n) scanf("%lld",&a[i]);
		
		fo(i,0,n+2) f[i]=g[i]=0;
		ans=0;
		fo(i,1,n) {
			x=a[i];
			if (x==0 || x==1) ans++;
			
			fo(j,-1,1) {
				if (x+j>=0) {
					add(ans, f[x+j]);
					if (j!=0) add(ans,g[x+j]);
				}
			}
			
			f[x+1]=f[x+1]*2ll%mo;
			g[x+1]=g[x+1]*2ll%mo;
			add(f[x+1],f[x]);
			
			if (x>0) {
				g[x-1]=g[x-1]*2ll%mo;
				add(g[x-1], f[x-1]);
			}


			if (!x) {
				add(f[1],1);
			}
			if (x==1) {	
				add(g[0],1);
			}
			
		}
		printf("%lld\n",ans);
	}
  	
	return 0;
}