代码

#include <vector>
#include <set>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <queue>

#define pb push_back
#define fi first
#define se second
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define ALL(a) a.begin(), a.end()
#define lowbit(x) ((x) & -(x))

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<ll, int> pii;
typedef pair<int, int> pi;
typedef vector<int> VI;

namespace io {
	const int L = (1 << 21) + 1;
	char ibuf[L], *iS, *iT, obuf[L], *oS = obuf, *oT = obuf + L - 1, c, qu[55]; int f, qr;
	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, L, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
	__attribute__((optimize("-O3")))
	void flush () { fwrite (obuf, 1, oS - obuf, stdout); oS = obuf; }
	__attribute__((optimize("-O3")))
	void putc (char x) { *oS ++ = x; if (oS == oT) flush (); }
	template <class I> __attribute__((optimize("-O3")))
	void gi (I & x) {
		for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
		for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
	}
	template <class I> __attribute__((optimize("-O3")))
	void print (I x) {
		if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
		while (x) qu[++ qr] = x % 10 + '0', x /= 10;
		while (qr) putc (qu[qr --]);
	}
	__attribute__((optimize("-O3")))
	char read () {
		for (c = gc(); c < 'a' || c > 'z'; c = gc());
		return c;
	}
	__attribute__((optimize("-O3")))
	void gs (char *s) {
		int l;
		for (c = gc(); c < 'a' || c > 'z'; c = gc());
		for (l = 0; c <= 'z' && c >= 'a'; c = gc()) s[l] = c, ++l;
		s[l] = 0;
	}
	__attribute__((optimize("-O3")))
	void ps (const char *s) {
		int l = strlen(s), i;
		for (i = 0; i < l; i ++) putc(s[i]);
	}
	struct IOC { ~ IOC () { flush (); } } _ioc_;
} ;
using io::gi;
using io::gs;
using io::ps;
using io::putc;
using io::read;
using io::print;

template <class T> __attribute__((optimize("-O3"))) 
bool chkmin(T &a, T b) { return b < a ? a = b, true : false; }
template <class T> __attribute__((optimize("-O3")))
bool chkmax(T &a, T b) { return a < b ? a = b, true : false; }

const int N = 1200005, P = 998244353;

__attribute__((optimize("-O3")))
int fpow(int a, int t){
	static int r;
	for (r = 1; t; t >>= 1, a = (ll)a * a % P) if (t & 1) r = (ll)r * a % P;
	return r;
}
int T, n, low, p[N], q[N], fac[N], ifac[N], inv[N], len[N], ret;
bool vis[N];
__attribute__((optimize("-O3")))
int binom(int n, int m){ return n < m ? 0 : (ll)fac[n] * ifac[m] % P * ifac[n - m] % P; }
__attribute__((optimize("-O3")))
int cal(int n, int m){
	return (binom(n + m, m) - binom(n + m, n + 1) + P) % P; 
}
__attribute__((optimize("-O3")))
int main(){
	freopen("inverse.in", "r", stdin), freopen("inverse.out", "w", stdout);
	int i, j, x;
	fac[0] = ifac[0] = fac[1] = ifac[1] = inv[1] = 1;
	for (i = 2; i < N; i ++) {
		fac[i] = (ll)fac[i - 1] * i % P;
		inv[i] = P - (ll)(P / i) * inv[P % i] % P;
		ifac[i] = (ll)ifac[i - 1] * inv[i] % P;
	}
	for (gi(T); T; --T) {
		gi(n);
		for (i = 1; i <= n; i ++) gi(p[i]);
		for (ret = j = 0, low = i = 1; i <= n; i ++) {
			chkmax(j, p[i]), len[n - i] = n - j;
			for (vis[p[i]] = true; vis[low]; ++low);
			if (p[i] < j && p[i] > low) break;
		}
		for (i = 0; i < n; i ++) {
			x = 0;
			if (i) chkmax(x, len[i - 1] - 1);
			for (j = x; j < len[i]; j ++) ret = (ret + binom(i + j, i)) % P;
			if (i == n - 1) for (j = 1; j < len[i]; j ++) ret = (ret - binom(i + j, j - 1)) % P;
		}
		ret = (ret + P) % P;
		print(ret), putc('\n');
		for (i = 1; i <= n; i ++) len[i - 1] = vis[i] = 0;
	}
	return 0;
}

评测结果