代码

#include <cstdio>
#include <cstring>

using namespace std;

typedef long long ll;

const int N = 600010;
const int P = 998244353;

int p[N];
int fac[N * 2], ifac[N * 2], inv[N * 2];
bool f[N];

void upd(int n);
int comb(int n, int m);
int schroder(int n, int m);

int main() {
	fac[0] = fac[1] = 1;
	ifac[0] = ifac[1] = 1;
	inv[1] = 1;
	int t;
	scanf("%d", &t);
	while (t--) {
		int n;
		scanf("%d", &n);
		for (int i = 1; i <= n; ++i)
			scanf("%d", &p[i]);
		upd(n * 2);
		int ans = 0, pa = 0, pb = 0, a = n, b = n;
		memset(f, 0, sizeof(bool) * (n + 1));
		for (int i = 1; i <= n; ++i) {
			if (p[i] > pa) {
				for (int j = pa + 1; j <= p[i]; ++j)
					if (!f[j])
						--a;
				ans += schroder(b, a - 1);
				if (ans >= P)
					ans -= P;
				pa = p[i];
			} else if (p[i] > pb) {
				if (a > 0) {
					ans += schroder(b, a - 1);
					if (ans >= P)
						ans -= P;
				}
				bool flag = true;
				for (int j = pb + 1; j < p[i]; ++j)
					if (!f[j]) {
						flag = false;
						break;
					}
				if (!flag)
					break;
				pb = p[i];
			}
			--b;
			f[p[i]] = true;
		}
		printf("%d\n", ans);
	}
	return 0;
}

void upd(int n) {
	static int mn = 1;
	if (mn >= n)
		return;
	for (int x = mn + 1; x <= n; ++x)
		inv[x] = -(P / x) * (ll)inv[P % x] % P + P;
	for (int x = mn + 1; x <= n; ++x)
		fac[x] = fac[x - 1] * (ll)x % P;
	for (int x = mn + 1; x <= n; ++x)
		ifac[x] = ifac[x - 1] * (ll)inv[x] % P;
	mn = n;
}

inline int comb(int n, int m) {
	if (m < 0)
		return 0;
	return fac[n] * (ll)ifac[m] % P * ifac[n - m] % P;
}

inline int schroder(int n, int m) {
	int ret = comb(n + m, m) - comb(n + m, m - 1);
	if (ret < 0)
		ret += P;
	return ret;
}

评测结果