代码

#include <cstdio>
#include <cstring>
#include <algorithm>

typedef long long LL;
const int N = 1200005, MOD = 998244353;

int tc, n;
int fac[N], ifac[N], p[N >> 1], len[N >> 1], vis[N >> 1];

inline int Pow(int x, int b) {
  static int re;
  for (re = 1; b; b >>= 1, x = (LL) x * x % MOD)
    if (b & 1) re = (LL) re * x % MOD;
  return re;
}

inline int C(int x, int y) {
  if (x < y) return 0;
  return (LL) fac[x] * ifac[y] % MOD * ifac[x - y] % MOD;
}

int main() {
  fac[0] = 1;
  for (int i = 1; i < N; ++i) {
    fac[i] = (LL) fac[i - 1] * i % MOD;
  }
  ifac[N - 1] = Pow(fac[N - 1], MOD - 2);
  for (int i = N - 1; i >= 1; --i) {
    ifac[i - 1] = (LL) ifac[i] * i % MOD;
  }
  
  scanf("%d", &tc);
  for (; tc; --tc) {
    int re = 0;
    memset(vis, 0, sizeof vis);
    memset(len, 0, sizeof len);
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
      scanf("%d", &p[i]);
    }
    for (int i = 1, low = 1, mx = 0; i <= n; ++i) {
      mx = std::max(mx, p[i]);
      len[n - i] = n - mx;
      for (vis[p[i]] = 1; vis[low]; ++low);
      if (mx > p[i] && p[i] > low) break;
    }
    for (int i = 0; i < n; ++i) {
      int x = 0;
      if (i > 0) x = std::max(x, len[i - 1] - 1);
      for (int j = x; j < len[i]; ++j) {
	re = (re + C(i + j, i)) % MOD;
      }
    }
    for (int i = 1; i < len[n - 1]; ++i) {
      re = (re - C(n - 1 + i, i - 1)) % MOD;
    }
    printf("%d\n", (re + MOD) % MOD);
  }

  return 0;
}

评测结果