代码

// NOI2018 冒泡排序 (noi18b) — count 321-avoiding permutations > q, mod 998244353
// O(n) per test (no BIT), direct-memory IO via DuckInfo.
#include <stdint.h>
#include <sys/auxv.h>

typedef unsigned int u32;
typedef unsigned long long u64;

static const u32 MOD = 998244353u;
static const u32 MAXN = 600000u;
static const u32 MAXF = 2u * MAXN; // n+k <= 2n-1, indices 0..2n

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));

static u32 fact[MAXF + 1];
static u32 invfact[MAXF + 1];
static unsigned char used[MAXN + 2];

static inline u32 read_u32(const char* &p) {
    while (*p < '0' || *p > '9') ++p;
    u32 x = 0;
    while (*p >= '0' && *p <= '9') { x = x * 10u + (u32)(*p - '0'); ++p; }
    return x;
}

static inline void write_u32(char* &o, u32 x) {
    char tmp[12];
    int n = 0;
    if (x == 0) { *o++ = '0'; }
    else {
        while (x) { tmp[n++] = (char)('0' + x % 10u); x /= 10u; }
        while (n--) *o++ = tmp[n];
    }
    *o++ = '\n';
}

static inline u32 T(u32 n, u32 k) {
    // (n-k+1)/(n+1) * C(n+k, k) = (n-k+1) * fact[n+k] * invfact[n+1] * invfact[k]
    u64 r = (u64)(n - k + 1) * fact[n + k] % MOD;
    r = r * invfact[n + 1] % MOD;
    r = r * invfact[k] % MOD;
    return (u32)r;
}

static inline u32 powmod(u32 a, u64 e) {
    u64 r = 1, b = a;
    while (e) { if (e & 1) r = r * b % MOD; b = b * b % MOD; e >>= 1; }
    return (u32)r;
}

int main() {
    DuckInfo* di = (DuckInfo*)getauxval(0x6b637564ull);
    const char* p = di->stdin_ptr;
    char* o = di->stdout_ptr;

    // Precompute factorials / inverse factorials up to 2*MAXN.
    u32* f = fact;
    f[0] = 1;
    for (u32 i = 1; i <= MAXF; ++i) f[i] = (u32)((u64)f[i - 1] * i % MOD);
    invfact[MAXF] = powmod(fact[MAXF], MOD - 2);
    for (u32 i = MAXF; i > 0; --i) invfact[i - 1] = (u32)((u64)invfact[i] * i % MOD);

    u32 Tn = read_u32(p);
    while (Tn--) {
        u32 n = read_u32(p);
        // reset used
        for (u32 i = 1; i <= n; ++i) used[i] = 0;
        u32 ans = 0;
        u32 mx = 0;      // max of prefix
        u32 mn = 1;      // smallest unused value
        u32 c = 0;       // count of unused values < mx
        u32 valid = 1;
        for (u32 i = 1; i <= n; ++i) {
            u32 qi = read_u32(p);
            if (!valid) continue; // consume rest, prefix already invalid
            u32 d = n - mx;
            u32 N = n - i;
            // record placements v in (max(mx,qi), n]
            u32 M;
            if (qi <= mx) M = d - 1;
            else M = n - 1 - qi;
            if ((int)M >= 0) {
                u32 t = T(N + 1, M);
                ans += t; if (ans >= MOD) ans -= MOD;
            }
            // min placement v = mn (only valid when a lower unused value exists)
            if (c >= 1 && mn > qi) {
                u32 t = T(N, d);
                ans += t; if (ans >= MOD) ans -= MOD;
            }
            // place qi; check prefix validity
            if (!(qi == mn || qi > mx)) { valid = 0; continue; }
            used[qi] = 1;
            if (qi > mx) { c += qi - mx - 1; mx = qi; }
            else c -= 1;
            if (qi == mn) {
                while (mn <= n && used[mn]) ++mn;
            }
        }
        write_u32(o, ans);
    }
    di->stdout_size = (u64)(o - di->stdout_ptr);
    return 0;
}

评测结果