代码

#include <cstdio>
#include <cstring>
#include <algorithm>
const int MAXN = 6e5 + 10;
const int MOD = 998244353;

int n;
int a[MAXN];
namespace solver1 {
  void main() {
    static int p[MAXN];
    for (int i = 1; i <= n; i++) p[i] = a[i];
    int ans = 0;
    while(std::next_permutation(p + 1, p + n + 1)) {
      static int tmp[MAXN];
      int c = 0, x = 0;
      for (int i = 1; i <= n; i++) tmp[i] = p[i], x += std::abs(i - p[i]);
      for (int i = 1; i <= n; i++) {
        for (int j = 1; j < n; j++) {
          if (tmp[j] > tmp[j + 1]) {
            std::swap(tmp[j], tmp[j + 1]);
            c++;
          }
        }
      }

      if (c == x / 2) ans++;
    }
    printf("%d\n", ans);
  }
}
namespace {
  inline int add(int x) { return x >= MOD ? x - MOD : x; }
  inline int sub(int x) { return x < 0 ? x + MOD : x; }
  inline int mul(int x, int y) { return (long long) x * y % MOD; }
  inline void add(int &x, int y) { x = add(x + y); }
  inline int pwr(int x, int y) {
    int ans = 1;
    for (; y; y >>= 1, x = mul(x, x)) {
      if (y & 1) ans = mul(ans, x);
    }
    return ans;
  }
}
namespace solver2 {
  int f[1 << 20 | 1][2];
  int bitcount(int x) { return x ? bitcount(x >> 1) + (x & 1) : 0; }
  void main() {
    memset(f, 0, sizeof f);
    f[0][0] = 1;
    for (int i = 0; i < (1 << n); i++) {
      for (int j = 0; j < 2; j++) {
        if (f[i][j]) {
          int cur = bitcount(i) + 1;
          for (int k = 1; k <= n; k++) {
            if (!j && k < a[cur]) continue;
            if (i & (1 << (k - 1))) continue;
            if (cur == k) {
              if (bitcount(i >> k)) continue;
              if (bitcount(~(i | (1 << (k - 1))) & ((1 << k) - 1))) continue;
            } else if (cur < k) {
              if (bitcount(i >> k)) continue;
            } else {
              if (bitcount(~(i | (1 << (k - 1))) & ((1 << k) - 1))) continue;
            }
            add(f[i | (1 << (k - 1))][j || (k > a[cur])], f[i][j]);
          }
        }
      }
    
    }
    printf("%d\n", f[(1 << n) - 1][1]);
  }
}
namespace solver_std {
  int fact[MAXN << 1], invf[MAXN << 1];
  void init(int n = 1.2e6) {
    fact[0] = invf[0] = 1;
    for (int i = 1; i <= n; i++) {
      fact[i] = mul(fact[i - 1], i);
      invf[i] = pwr(fact[i], MOD - 2);
    }
  }
  int choose(int x, int y) {
    return x < y ? 0 : mul(fact[x], mul(invf[x - y], invf[y]));
  }
  int calc(int x, int y) {
    if (x < y) return 0;
    return sub(choose(x + y, x) - choose(x + y, x + 1));
  }
  void main() {

    int ans = 0;
    int y = n, max = 0;
    static int min[MAXN];

    min[n] = a[n];

    for (int i = n - 1; i >= 1; i--) {
      min[i] = std::min(min[i + 1], a[i]);
    }

    for (int i = 1; i <= n; i++) {
      if (a[i] > max) {
        y = n - a[i];
        max = a[i];
        add(ans, calc(n - i + 1, y - 1));
      } else {
        add(ans, calc(n - i + 1, y - 1));
        //if (y == n - i + 1) break; 
        if (a[i] != min[i]) break;
      }
    }
    printf("%d\n", ans);
                                  
  }
}
int main() {
#ifndef LOCAL
  freopen("inverse.in", "r", stdin); 
  freopen("inverse.out", "w", stdout);
#endif
  int t;
  scanf("%d", &t);
  
  solver_std::init();
  
  while(t--) {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
      scanf("%d", a + i);
    }
    /*
    if (n <= 9) solver1::main();
    else solver2::main();
    */
    solver_std::main();
  }
}

评测结果