代码

#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]);
  }
}
int main() {
#ifndef LOCAL
  freopen("inverse.in", "r", stdin);
  freopen("inverse.out", "w", stdout);
#endif
  int t;
  scanf("%d", &t);
  while(t--) {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
      scanf("%d", a + i);
    }
    if (n <= 9) solver1::main();
    else solver2::main();
  }
}

评测结果