代码

#include<cstdio>
#include<bitset>

using namespace std;

const int N = 6e5 + 10;
const int mod = 998244353;

bitset<N> vis;

int fac[N << 1], ifac[N << 1], q[N];

int qpow(int a, int x) {
	int ret = 1;
	while(x) {
		if(x & 1) ret = 1ll * ret * a % mod;
		x >>= 1, a = 1ll * a * a % mod;
	}
	return ret;
}

void Math_Init(int n) {
	fac[0] = 1;
	for(int i = 1; i <= n; ++ i)
		fac[i] = 1ll * fac[i - 1] * i % mod;
	ifac[n] = qpow(fac[n], mod - 2);
	for(int i = n; i >= 1; -- i)
		ifac[i - 1] = 1ll * ifac[i] * i % mod;
}

int C(int n, int m) {
	return n < m ? 0 : 1ll * fac[n] * ifac[n - m] % mod * ifac[m] % mod;
}

int cal(int x, int y) {
	return x > y ? 0 : (C(x + y, y) + mod - C(x + y, y + 1)) % mod;
}

int main() {
#ifdef ylsakioi
	freopen("4769.in", "r", stdin);
	freopen("4769.out", "w", stdout);
#endif

	Math_Init((N - 5) << 1);

	int t, n, ans = 0;

	for(scanf("%d", &t); t -- ; ans = 0, vis.reset()) {

		scanf("%d", &n);
		for(int i = 1; i <= n; ++ i)
			scanf("%d", &q[i]);

		int mn = 1, mx = 0, left = 0;

		for(int i = 1; i <= n; ++ i, -- left) {
			if(q[i] > mx) left += q[i] - mx, mx = q[i];
			(ans += cal(n - i - left, n - i + 1)) %= mod;
			if(mn < q[i] && q[i] < mx) break;
			for(vis[q[i]] = 1; vis[mn]; ++ mn) ;
		}

		printf("%d\n", ans);
	}
	return 0;
}

评测结果