代码

#ifndef DUCK_FASTIO_H
#define DUCK_FASTIO_H

typedef unsigned long duck_u64;
typedef long duck_i64;

typedef struct {
    duck_u64 abi_version;
    const char *stdin_ptr;
    duck_u64 stdin_size;
    char *stdout_ptr;
    duck_u64 stdout_limit;
    duck_u64 stdout_size;
    char *stderr_ptr;
    duck_u64 stderr_limit;
    duck_u64 stderr_size;
    const char *ib_ptr;
    duck_u64 ib_limit;
    char *ob_ptr;
    duck_u64 ob_limit;
    duck_u64 tsc_frequency;
} __attribute__((packed)) DuckInfo;

static __attribute__((always_inline)) inline DuckInfo *duck_info(long argc, char **argv) {
    char **p = argv + argc + 1;
    while (*p) ++p;
    duck_u64 *aux = (duck_u64 *)(p + 1);
    while (aux[0]) {
        if (aux[0] == 0x6b637564UL) return (DuckInfo *)aux[1];
        aux += 2;
    }
    return (DuckInfo *)0;
}

static __attribute__((always_inline)) inline duck_u64 duck_read_u64(const char **cursor) {
    const char *p = *cursor;
    while ((unsigned char)(*p - '0') > 9) ++p;
    duck_u64 value = 0;
    do {
        value = value * 10 + (unsigned char)(*p - '0');
        ++p;
    } while ((unsigned char)(*p - '0') <= 9);
    *cursor = p;
    return value;
}

static __attribute__((always_inline)) inline duck_i64 duck_read_i64(const char **cursor) {
    const char *p = *cursor;
    while (*p != '-' && (unsigned char)(*p - '0') > 9) ++p;
    int negative = *p == '-';
    p += negative;
    duck_u64 value = 0;
    do {
        value = value * 10 + (unsigned char)(*p - '0');
        ++p;
    } while ((unsigned char)(*p - '0') <= 9);
    *cursor = p;
    return negative ? -(duck_i64)value : (duck_i64)value;
}

static __attribute__((always_inline)) inline char *duck_write_u64(char *out, duck_u64 value) {
    char tmp[24];
    unsigned n = 0;
    do {
        tmp[n++] = (char)('0' + value % 10);
        value /= 10;
    } while (value);
    do *out++ = tmp[--n]; while (n);
    return out;
}

static __attribute__((always_inline)) inline char *duck_write_i64(char *out, duck_i64 value) {
    if (value < 0) {
        *out++ = '-';
        return duck_write_u64(out, (duck_u64)(-value));
    }
    return duck_write_u64(out, (duck_u64)value);
}

static __attribute__((always_inline, noreturn)) inline void duck_exit(void) {
    __asm__ volatile("mov $60,%%eax;xor %%edi,%%edi;syscall" ::: "rax", "rdi", "rcx", "r11", "memory");
    __builtin_unreachable();
}

#endif


#define MOD 998244353u
#define MAXF 1200002

typedef unsigned int u32;
typedef unsigned long u64;

static u32 fac[MAXF], ifac[MAXF];
static unsigned char used[600002];

static __attribute__((always_inline)) inline u32 rd(const char **pp) {
    const char *p = *pp;
    while ((unsigned char)*p <= ' ') ++p;
    u32 x = 0;
    while ((unsigned)(*p - '0') < 10) x = x * 10u + (u32)(*p++ - '0');
    *pp = p;
    return x;
}

static __attribute__((always_inline)) inline u32 mul(u32 a, u32 b) {
    return (u32)((u64)a * b % MOD);
}

static u32 power(u32 a, u32 e) {
    u32 r = 1;
    while (e) {
        if (e & 1) r = mul(r, a);
        a = mul(a, a);
        e >>= 1;
    }
    return r;
}

static __attribute__((always_inline)) inline u32 choose(u32 n, u32 k) {
    if (k > n) return 0;
    return mul(fac[n], mul(ifac[k], ifac[n - k]));
}

static __attribute__((always_inline)) inline char *putu(char *p, u32 x) {
    char s[12];
    u32 n = 0;
    do { s[n++] = (char)('0' + x % 10); x /= 10; } while (x);
    do { *p++ = s[--n]; } while (n);
    *p++ = '\n';
    return p;
}

__attribute__((noreturn))
void __libc_start_main(void *unused, long argc, char **argv) {
    (void)unused;
    DuckInfo *info = duck_info(argc, argv);
    const char *p = info->stdin_ptr;
    u32 T = rd(&p), maxn = 0;
    const char *scan = p;
    for (u32 tc = 0; tc < T; ++tc) {
        u32 n = rd(&scan);
        if (n > maxn) maxn = n;
        for (u32 i = 0; i < n; ++i) (void)rd(&scan);
    }

    u32 top = maxn << 1;
    fac[0] = 1;
    for (u32 i = 1; i <= top; ++i) fac[i] = mul(fac[i - 1], i);
    ifac[top] = power(fac[top], MOD - 2);
    for (u32 i = top; i; --i) ifac[i - 1] = mul(ifac[i], i);

    char *out = info->stdout_ptr;
    for (u32 tc = 0; tc < T; ++tc) {
        u32 n = rd(&p), mx = 0, mn = 1, ans = 0;
        int valid = 1;
        __builtin_memset(used, 0, n + 2);
        for (u32 i = 1; i <= n; ++i) {
            u32 x = rd(&p);
            if (!valid) continue;
            u32 lim = mx + 1;
            if (lim <= x) lim = x + 1;
            used[x] = 1;
            if (lim <= n) {
                u32 a = 2 * n - i - lim + 1;
                u32 v1 = choose(a, n - i + 1);
                u32 v2 = choose(a, n - i + 2);
                ans += v1 >= v2 ? v1 - v2 : v1 + MOD - v2;
                if (ans >= MOD) ans -= MOD;
            }
            if (x > mx) mx = x;
            else if (x != mn) valid = 0;
            while (mn <= n && used[mn]) ++mn;
        }
        out = putu(out, ans);
    }
    info->stdout_size = (unsigned long)(out - info->stdout_ptr);
    duck_exit();
}

int main(void) {}

评测结果