代码

#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;
}
const int N=1200005,mod=998244353;
int fc[N]={1},ic[N]={1},n;bool vs[N>>1];
inline int u(int a,int b){
	int ret;__asm__ __volatile__(
		"\tmull %%ebx\n\tdivl %%ecx\n":
		"=d"(ret):"a"(a),"b"(b),"c"(mod));
	return ret;
}
inline int inv(int x){
	int ret=1;
	for(int b=mod-2;b;b>>=1,x=u(x,x))
		if(b&1) ret=u(ret,x);
	return ret;
}
inline int c(int n,int m){
	if(n<m) return 0;
	return u(fc[n],u(ic[n-m],ic[m]));
}
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(){
	for(int i=1;i<N;++i) fc[i]=u(fc[i-1],i);
	ic[N-1]=inv(fc[N-1]);
	for(int i=N-1;i>1;--i) ic[i-1]=u(ic[i],i);
	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;
}

评测结果