代码

// This code is AI-generated. (AI 生成的代码)
// NOI2018 冒泡排序: count permutations via the standard binomial sum; stop at
// the first position that makes the given permutation unrealizable.
#include <stdio.h>
#include <string.h>
typedef long long ll;
enum { N = 1200005, MOD = 998244353 };
static int fc[N], ic[N], n;
static char vs[N];
static ll pw(ll a, ll b) { ll r = 1; a %= MOD; while (b) { if (b & 1) r = r * a % MOD; a = a * a % MOD; b >>= 1; } return r; }
static inline int C(int a, int b) {
    if (b < 0 || b > a) return 0;
    return (ll)fc[a] * ic[b] % MOD * ic[a - b] % MOD;
}
static inline int f(int i, int q) {
    int a = (n << 1) - i - q, b = n - i + 1;
    int r = C(a, b) - C(a, b + 1);
    return r < 0 ? r + MOD : r;
}
static char ib[1 << 25], ob[1 << 16];
static char *gp;
static inline int rd() { while ((unsigned)(*gp - '0') > 9u) gp++; int v = 0; while ((unsigned)(*gp - '0') <= 9u) v = v * 10 + (*gp++ - '0'); return v; }
int main() {
    fc[0] = 1;
    for (int i = 1; i < N; i++) fc[i] = (ll)fc[i - 1] * i % MOD;
    ic[N - 1] = (int)pw(fc[N - 1], MOD - 2);
    for (int i = N - 1; i > 0; i--) ic[i - 1] = (ll)ic[i] * i % MOD;
    int len = (int)fread(ib, 1, sizeof(ib) - 1, stdin);
    ib[len] = 0; gp = ib;
    char *op = ob;
    int T = rd();
    while (T--) {
        n = rd();
        memset(vs + 1, 0, n + 1);
        int ans = 0, mx = 0, ps = 1, i, x, t;
        for (i = 1; i <= n; i++) {
            x = rd(); vs[x] = 1;
            t = x > mx ? x : mx;
            ans += f(i, t);
            if (ans >= MOD) ans -= MOD;
            if (x < mx && ps < x) break;
            while (ps <= n && vs[ps]) ps++;
            mx = t;
        }
        for (; i < n; i++) rd();
        char tmp[12]; int k = 0;
        if (!ans) tmp[k++] = '0';
        while (ans) { tmp[k++] = (char)('0' + ans % 10); ans /= 10; }
        while (k) *op++ = tmp[--k];
        *op++ = '\n';
    }
    fwrite(ob, 1, op - ob, stdout);
    return 0;
}

评测结果