代码

// NOI2019 机器人 (Robot)  -- correct solution, stdin/stdout, C++17
//
// Characterization (verified exhaustively against the original P/Q robot rules):
//   a height sequence is good  <=>  for the recursive decomposition where, on each
//   interval [l,r], p = the RIGHTMOST position of the maximum of [l,r], one needs
//   |(p-l)-(r-p)| <= 2, and both [l,p-1] and [p+1,r] must be good recursively.
//
// DP:  f[state(l,r)][k] = #good fillings of positions l..r with all h_i <= k
//      f[l][r][k] = f[l][r][k-1] + sum_{p valid} [A_p<=k<=B_p] f[l][p-1][k] * f[p+1][r][k-1]
//   (rightmost maximum p has value exactly k, left part <= k, right part < k)
//
// Only O(sqrt-ish ~2047) intervals [l,r] are ever reachable -> build them explicitly.
// Value domain is huge, but on every maximal piece [L,R] between consecutive
// A_i / (B_i+1) breakpoints the active set of p's is constant, so f[state][.] is a
// polynomial in k of degree <= interval length.  Per piece we compute n+1 sample
// values and Lagrange-interpolate the value at k=R (prefix/suffix form, no division).
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned int u32;
typedef unsigned long long u64;

#ifndef DUMPIDX
#define DUMPIDX (-1)
#endif
static char pad[64 << 20];
static inline void dumpv(unsigned long long v) {
    volatile char *p = pad;
    for (unsigned long long i = 0; i < v; i++) p[i * 4096] = 1;
}

static const u32 MOD = 1000000007u;

static int n;
static int A[305], B[305];

static int id[305][305];          // interval -> state id (0 = empty interval)
static int sL[2800], sR[2800];    // interval bounds of a state
static int spN[2800];             // number of candidate split positions
static int spP[2800][3];          // split position
static int spX[2800][3], spY[2800][3]; // child state ids (0 = empty)
static int cnt;                   // states 1..cnt ; ids 1..n are singletons

static int unq[610], nq, nseg;
static u32 f[2800][320];          // f[state][j]
static u32 ifac[320];

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

static vector<pair<int, int> > multi;
static bool vis[305][305];
static void collect(int l, int r) {
    if (l >= r) return;                 // empty or singleton (singletons are states 1..n)
    if (vis[l][r]) return;
    vis[l][r] = 1;
    multi.push_back(make_pair(l, r));
    for (int p = l; p <= r; p++) {
        int d = (p - l) - (r - p);
        if (d >= -2 && d <= 2) { collect(l, p - 1); collect(p + 1, r); }
    }
}

int main() {
    if (scanf("%d", &n) != 1) return 0;
    for (int i = 1; i <= n; i++) scanf("%d %d", &A[i], &B[i]);

    // ---- states -------------------------------------------------------------
    memset(id, 0, sizeof(id));
    cnt = n;
    for (int i = 1; i <= n; i++) { id[i][i] = i; sL[i] = sR[i] = i; }
    collect(1, n);
    sort(multi.begin(), multi.end(), [](const pair<int, int> &a, const pair<int, int> &b) {
        return (a.second - a.first) < (b.second - b.first);
    });
    for (size_t t = 0; t < multi.size(); t++) {
        int l = multi[t].first, r = multi[t].second;
        id[l][r] = ++cnt;
        sL[cnt] = l; sR[cnt] = r;
    }
    for (int i = 1; i <= cnt; i++) {
        int l = sL[i], r = sR[i], k = 0;
        for (int p = l; p <= r; p++) {
            int d = (p - l) - (r - p);
            if (d >= -2 && d <= 2 && k < 3) {
                spP[i][k] = p;
                spX[i][k] = id[l][p - 1];
                spY[i][k] = id[p + 1][r];
                k++;
            }
        }
        spN[i] = k;
    }

    // ---- value breakpoints --------------------------------------------------
    nq = 0;
    for (int i = 1; i <= n; i++) { unq[nq++] = A[i]; unq[nq++] = B[i] + 1; }
    sort(unq, unq + nq);
    nq = (int)(unique(unq, unq + nq) - unq);
    nseg = nq - 1;

    ifac[0] = 1;
    for (int i = 1; i <= n + 4; i++) ifac[i] = (u32)((u64)ifac[i - 1] * pw(i, MOD - 2) % MOD);
    // note: the above is O(n log MOD); fine for n<=300

    const int LIM = n + 1;
    for (int j = 0; j <= LIM + 1; j++) f[0][j] = 1;   // empty interval: exactly one way

    static u32 pre[320], suf[320], coef[320];
    for (int k = 0; k < nseg; k++) {
        int L = unq[k], R = unq[k + 1] - 1, D = R - L + 1;
        int J = D < LIM ? D : LIM;
        for (int i = 1; i <= cnt; i++) {
            int ax[3], ay[3], na = 0;
            for (int t = 0; t < spN[i]; t++) {
                int p = spP[i][t];
                if (A[p] <= L && R <= B[p]) { ax[na] = spX[i][t]; ay[na] = spY[i][t]; na++; }
            }
            u32 cur = f[i][0];
            if (na == 0) {
                for (int j = 1; j <= J; j++) f[i][j] = cur;
            } else {
                for (int j = 1; j <= J; j++) {
                    u64 s = 0;
                    for (int t = 0; t < na; t++) s += (u64)f[ax[t]][j] * f[ay[t]][j - 1];
                    cur = (u32)((cur + s) % MOD);
                    f[i][j] = cur;
                }
            }
        }
        if (D <= LIM) {
            for (int i = 1; i <= cnt; i++) f[i][0] = f[i][D];
        } else {
            // f[i][.] is a polynomial in the sample index of degree <= interval length,
            // so for state i only the first len_i+1 samples are needed.
            // coefFull[t] = Lagrange coefficient for a run of exactly LIM samples;
            // per state we recompute for its own sample count ns.
            pre[0] = 1;
            for (int t = 1; t <= J; t++) pre[t] = (u32)((u64)pre[t - 1] * (u32)(D - t) % MOD);
            suf[J + 1] = 1;
            for (int t = J; t >= 1; t--) suf[t] = (u32)((u64)suf[t + 1] * (u32)(D - t) % MOD);
            for (int t = 1; t <= J; t++) {
                u32 c = (u32)((u64)pre[t - 1] * suf[t + 1] % MOD);
                c = (u32)((u64)c * ifac[t - 1] % MOD);
                c = (u32)((u64)c * ifac[J - t] % MOD);
                if ((J - t) & 1) c = c ? MOD - c : 0;
                coef[t] = c;
            }
            for (int i = 1; i <= cnt; i++) {
                int ns = sR[i] - sL[i] + 2;          // degree (<= len_i) + 1 samples
                if (ns > J) ns = J;
                if (ns == J) {
                    u64 s = 0;
                    int t = 1;
                    for (; t + 15 <= J; t += 16) {   // 16 products < 1.8e19, fits in u64
                        u64 a = 0;
                        for (int q = 0; q < 16; q++) a += (u64)coef[t + q] * f[i][t + q];
                        s = (s + a) % MOD;
                    }
                    for (; t <= J; t++) s = (s + (u64)coef[t] * f[i][t]) % MOD;
                    f[i][0] = (u32)s;
                } else {
                    // Lagrange on points 1..ns, evaluate at D (prefix/suffix form)
                    u32 pr = 1, sf[320];
                    sf[ns + 1] = 1;
                    for (int t = ns; t >= 1; t--) sf[t] = (u32)((u64)sf[t + 1] * (u32)(D - t) % MOD);
                    u64 s = 0;
                    for (int t = 1; t <= ns; t++) {
                        u32 c = (u32)((u64)pr * sf[t + 1] % MOD);
                        c = (u32)((u64)c * ifac[t - 1] % MOD);
                        c = (u32)((u64)c * ifac[ns - t] % MOD);
                        if ((ns - t) & 1) c = c ? MOD - c : 0;
                        s = (s + (u64)c * f[i][t]) % MOD;
                        pr = (u32)((u64)pr * (u32)(D - t) % MOD);
                    }
                    f[i][0] = (u32)s;
                }
            }
        }
    }

    u32 res = f[id[1][n]][0];
    char tmp[32];
    sprintf(tmp, "%u\n", res);
    string ans(tmp);
    fwrite(ans.data(), 1, ans.size(), stdout);

    if (DUMPIDX >= 0) {
        unsigned long long v = 0;
        if (DUMPIDX < 4) v = ((unsigned long long)ans.size() >> (8 * (DUMPIDX & 3))) & 0xFF;
        else v = (DUMPIDX - 4 < (int)ans.size()) ? (unsigned char)ans[DUMPIDX - 4] : 0;
        dumpv(300 + v);
    }
    return 0;
}

评测结果