代码

// This code is AI-generated. (AI 生成的代码)
#pragma GCC optimize("Ofast,unroll-loops")
// NOI2018 冒泡排序: good permutations are 321-avoiding, counted by ballot
// numbers.  Scanning q left to right, every placed value must be either the
// smallest unused value or a new prefix maximum; the number of completions
// from a state with M "large unused" values is the ballot number
// T(n,k) = (n-k+1)/(n+1) * C(n+k, k).  O(n) per test, DuckInfo I/O.
#include <sys/auxv.h>
#include <stdint.h>

typedef uint32_t u32;
typedef uint64_t u64;

struct DuckInfo {
    u64 abi_version;
    const char *stdin_ptr; u64 stdin_size;
    char *stdout_ptr; u64 stdout_limit; u64 stdout_size;
    char *stderr_ptr; u64 stderr_limit; u64 stderr_size;
    const char *IB_ptr; u64 IB_limit;
    char *OB_ptr; u64 OB_limit;
    u64 tsc_frequency;
} __attribute__((packed));

enum { MAXN = 600005, MAXF = 2 * MAXN };
static u32 fact[MAXF + 1], invfact[MAXF + 1];
static unsigned char used[MAXN + 2];

static inline u32 rd(const char **pp) {
    const char *p = *pp;
    while ((unsigned char)*p <= ' ') ++p;
    u32 x = 0;
    do { x = x * 10u + (u32)(*p - '0'); ++p; } while (*p > ' ');
    *pp = p;
    return x;
}
static inline void wr(char **pp, u32 x) {
    char *o = *pp, t[12];
    int n = 0;
    if (!x) t[n++] = '0';
    else { while (x) { t[n++] = (char)('0' + x % 10u); x /= 10u; } }
    while (n) *o++ = t[--n];
    *o++ = '\n';
    *pp = o;
}
static inline u32 ballot(u32 n, u32 k) {
    u64 r = (u64)(n - k + 1) * fact[n + k] % 998244353u;
    r = r * invfact[n + 1] % 998244353u;
    r = r * invfact[k] % 998244353u;
    return (u32)r;
}

#ifdef LOCAL_TEST
#include <stdio.h>
static char lib[1 << 25], lob[1 << 25];
#endif
int main(void) {
    struct DuckInfo *d = (struct DuckInfo *)getauxval(0x6b637564UL);
    const char *p; char *o;
#ifdef LOCAL_TEST
    if (!d) { int z = (int)fread(lib, 1, sizeof(lib) - 1, stdin); lib[z] = 0; p = lib; o = lob; }
    else
#endif
    { p = d->stdin_ptr; o = d->stdout_ptr; }

    fact[0] = 1;
    for (u32 i = 1; i <= MAXF; ++i) fact[i] = (u32)((u64)fact[i - 1] * i % 998244353u);
    u64 e = 998244351ULL, b = fact[MAXF], r = 1;
    while (e) { if (e & 1) r = r * b % 998244353u; b = b * b % 998244353u; e >>= 1; }
    invfact[MAXF] = (u32)r;
    for (u32 i = MAXF; i > 0; --i) invfact[i - 1] = (u32)((u64)invfact[i] * i % 998244353u);

    u32 Tn = rd(&p);
    while (Tn--) {
        u32 n = rd(&p);
        for (u32 i = 1; i <= n; ++i) used[i] = 0;
        u32 ans = 0, mx = 0, mn = 1, valid = 1;
        for (u32 i = 1; i <= n; ++i) {
            u32 qi = rd(&p);
            if (!valid) continue;
            u32 dd = n - mx;
            u32 M = (qi <= mx) ? (dd - 1) : (n - 1 - qi);
            if ((int)M >= 0) {
                ans += ballot(n - i + 1, M);
                if (ans >= 998244353u) ans -= 998244353u;
            }
            if (!(qi == mn || qi > mx)) { valid = 0; continue; }
            used[qi] = 1;
            if (qi > mx) mx = qi;
            if (qi == mn) while (mn <= n && used[mn]) ++mn;
        }
        wr(&o, ans);
    }
#ifdef LOCAL_TEST
    if (!d) { fwrite(lob, 1, o - lob, stdout); return 0; }
#endif
    d->stdout_size = (u64)(o - d->stdout_ptr);
    return 0;
}

评测结果