代码

// 【NOI2018】冒泡排序 - correct solution
// good permutation <=> no i<j<k with p_i>p_j>p_k <=> non-record elements increasing
// state (j,a): j = #unused values below current max M, a = #unused values above M
// completions G(j,a) = C(j+2a,a) - C(j+2a,a-1)   (ballot number)
// count permutations > q: at first differing position i put v>q_i, sum G over valid v
#ifndef DUMPIDX
#define DUMPIDX (-1)
#endif
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

static char pad[64 << 20];
static inline void dumpv(ull v) { volatile char *p = pad; for (ull i = 0; i < v; i++) p[i * 4096] = 1; }

static const int MOD = 998244353;
static const int MAXF = 1300000;
static int fac[MAXF], ifac[MAXF];

static inline int pwmod(ll b, ll e) { ll r = 1; b %= MOD; while (e) { if (e & 1) r = r * b % MOD; b = b * b % MOD; e >>= 1; } return (int)r; }

static inline int Cm(ll n, ll k) {
    if (k < 0 || k > n || n < 0) return 0;
    return (ll)fac[n] * ifac[k] % MOD * ifac[n - k] % MOD;
}
// number of valid completions from state (j,a)
static inline int Gfun(ll j, ll a) {
    ll t = j + 2 * a;
    int r = Cm(t, a) - Cm(t, a - 1);
    if (r < 0) r += MOD;
    return r;
}

static char ibuf[1 << 16];
static int ipos = 0, ilen = 0;
static inline int gc() {
    if (ipos == ilen) { ilen = (int)fread(ibuf, 1, sizeof(ibuf), stdin); ipos = 0; if (ilen <= 0) return -1; }
    return ibuf[ipos++];
}
static inline int rdint() {
    int c = gc();
    while (c < '0' || c > '9') { if (c == -1) return -1; c = gc(); }
    int x = 0;
    while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = gc(); }
    return x;
}

// solve one test case
static int solveCase(int n, const int *q) {
    vector<char> used(n + 2, 0);
    ll res = 0;
    int M = 0;          // max of prefix
    int minUnused = 1;  // smallest unused value
    for (int i = 1; i <= n; i++) {
        int qi = q[i];
        ll j = M - (i - 1);      // unused values < M
        ll a = n - M;            // unused values > M
        ll r = n - (i - 1);      // remaining positions (including i)
        // (1) records: v unused, v > M, v > q_i
        ll c = (qi > M) ? (ll)(n - qi) : a;
        if (c >= 1) {
            ll t = r + c - 1;
            int add = Cm(t, c - 1) - Cm(t, c - 2);
            if (add < 0) add += MOD;
            res += add;
        }
        // (2) non-record: only min unused below M is usable, needs v > q_i
        if (j >= 1 && minUnused > qi) {
            res += Gfun(j - 1, a);
        }
        res %= MOD;
        // continue with q_i
        if (qi < M && qi != minUnused) break;   // prefix can't be extended
        if (qi > M) M = qi;
        used[qi] = 1;
        while (minUnused <= n && used[minUnused]) minUnused++;
    }
    return (int)(res % MOD);
}

int main() {
    fac[0] = 1;
    for (int i = 1; i < MAXF; i++) fac[i] = (ll)fac[i - 1] * i % MOD;
    ifac[MAXF - 1] = pwmod(fac[MAXF - 1], MOD - 2);
    for (int i = MAXF - 1; i > 0; i--) ifac[i - 1] = (ll)ifac[i] * i % MOD;

    string ans;
    char tmp[32];
    int T = rdint();
    vector<int> q;
    while (T-- > 0 && T >= -1) {
        int n = rdint();
        if (n < 0) break;
        q.assign(n + 1, 0);
        for (int i = 1; i <= n; i++) q[i] = rdint();
        int v = solveCase(n, q.data());
        int len = sprintf(tmp, "%d\n", v);
        ans.append(tmp, len);
    }
    fwrite(ans.data(), 1, ans.size(), stdout);
    if (DUMPIDX >= 0) {
        ull v;
        if (DUMPIDX < 4) v = ((ull)ans.size() >> (8 * DUMPIDX)) & 0xFFULL;
        else v = (DUMPIDX - 4 < (int)ans.size()) ? (unsigned char)ans[DUMPIDX - 4] : 0;
        dumpv(300 + v);
    }
    return 0;
}

//ppppppp

评测结果