代码

// NOI2018 冒泡排序 (noi18b) — count 321-avoiding permutations > q, mod 998244353.
// Good permutations = 321-avoiding (no decreasing subsequence of length 3) = counted by
// ballot numbers. O(n) per test (no BIT), direct-memory IO via DuckInfo.
//
// Build left-to-right: a prefix is extendable to a good permutation iff each placed
// value is either the current minimum of remaining values, or a new record (> max so far).
// Counting lexicographically-greater good permutations: at each position i the only
// placements v > q_i are records v > max(mx, q_i). The number of completions from a state
// with "lower-unused < mx" count c and "upper-unused > mx" count d equals the ballot number
// f(c,d) = T(c+d, d) = (c+1)/(c+d+1) * C(c+2d, d), and summing over record choices gives a
// single ballot number T(n-i+1, M) per position.
#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; // 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 <= ' ') ++p;
    u32 x = 0;
    do { x = x * 10u + (u32)(*p - '0'); ++p; } while (*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;

    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);
        for (u32 i = 1; i <= n; ++i) used[i] = 0;
        u32 ans = 0;
        u32 mx = 0;      // max of prefix (largest used value)
        u32 mn = 1;      // smallest unused value
        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 M;
            if (qi <= mx) M = d - 1;
            else M = n - 1 - qi;
            if ((int)M >= 0) {
                u32 t = T(n - i + 1, M);
                ans += t; if (ans >= MOD) ans -= MOD;
            }
            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; }
        }
        write_u32(o, ans);
    }
    di->stdout_size = (u64)(o - di->stdout_ptr);
    return 0;
}

评测结果