代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define _(d) while(d((ch=getchar()-48)>=0))
inline int get(){
	char ch;_(!);int x=ch;
	_() x=(x<<3)+(x<<1)+ch;
	return x;
}
typedef long long ll;
const int N=1200005,mod=998244353;
int fc[N],ic[N],n;bool vs[N>>1];
inline int inv(int x){
	int ret=1;
	for(int b=mod-2;b;b>>=1,x=ll(x)*x%mod)
		if(b&1) ret=ll(ret)*x%mod;
	return ret;
}
inline int c(int n,int m){
	if(n<m) return 0;
	return ll(fc[n])*ic[n-m]%mod*ic[m]%mod;
}
inline int f(int i,int q){
	int a=(n<<1)-i-q,b=n-i+1;
	b=c(a,b)-c(a,b+1);
	return b<0?b+mod:b;
}
int main(){
	fc[0]=ic[0]=1; 
	for(int i=1;i<N;++i) fc[i]=fc[i-1]*ll(i)%mod;
	ic[N-1]=inv(fc[N-1]);
	for(int i=N-1;i>1;--i) ic[i-1]=ic[i]*ll(i)%mod;
	for(int T=get();T--;){
		memset(vs+1,0,n=get());
		int ans=0,mx=0,ps=1,i,x,t;
		for(i=1;i<=n;++i,mx=t){
			vs[x=get()]=1;
			if((ans+=f(i,t=max(x,mx)))>=mod) ans-=mod;
			if(x<mx&&ps<x) break;
			for(;vs[ps];++ps);
		}while(i<n) ++i,get();
		printf("%d\n",ans);
	}
	return 0;
}

评测结果