代码

/* NOI 2019 robot -- sparse interval DP over piecewise polynomials.
 * Polynomials are stored by values at 0..n+1.  Lagrange weights for the
 * (few) endpoints actually queried are cached, making evaluation a dot product.
 */
#include <algorithm>
#include <array>
#include <cstdint>
#include <cstring>
#include <utility>
#include <vector>

#ifdef LOCAL
#include <cstdio>
#endif

using u64 = unsigned long;
using u128 = unsigned __int128;
constexpr int MOD = 1000000007;
constexpr int INF = 1073741823;
constexpr int MAX_N = 300;
constexpr int MAX_S = MAX_N + 2;
constexpr int HASH_SIZE = 32768;
constexpr int MAX_WEIGHTS = 18000;

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 int n, sample_count;
static int low_bound[MAX_N + 1], high_bound[MAX_N + 1];
static int invfac[MAX_S];
static int weight_key[HASH_SIZE], weight_slot[HASH_SIZE];
static int weights[MAX_WEIGHTS][MAX_S];
static int weight_count;

static inline DuckInfo *duck_info(long argc, char **argv) {
    char **p = argv + argc + 1;
    while (*p) ++p;
    u64 *aux = reinterpret_cast<u64 *>(p + 1);
    while (aux[0]) {
        if (aux[0] == 0x6b637564UL) return reinterpret_cast<DuckInfo *>(aux[1]);
        aux += 2;
    }
    return nullptr;
}

static inline unsigned read_uint(const char *&p) {
    while (static_cast<unsigned>(*p - '0') > 9) ++p;
    unsigned x = 0;
    do x = x * 10u + static_cast<unsigned>(*p++ - '0');
    while (static_cast<unsigned>(*p - '0') <= 9);
    return x;
}

static inline int add_mod(int a, int b) {
    int x = a + b;
    return x >= MOD ? x - MOD : x;
}

static inline int sub_mod(int a, int b) {
    int x = a - b;
    return x < 0 ? x + MOD : x;
}

static int mod_pow(int x, int e) {
    int r = 1;
    while (e) {
        if (e & 1) r = static_cast<int>(static_cast<long long>(r) * x % MOD);
        x = static_cast<int>(static_cast<long long>(x) * x % MOD);
        e >>= 1;
    }
    return r;
}

/* Return cached Lagrange weights for nodes 0..sample_count-1 at x. */
static const int *get_weights(int raw_x) {
    int x = raw_x % MOD;
    unsigned h = static_cast<unsigned>(x) * 2654435761u & (HASH_SIZE - 1);
    while (weight_slot[h]) {
        int slot = weight_slot[h] - 1;
        if (weight_key[h] == x) return weights[slot];
        h = (h + 1) & (HASH_SIZE - 1);
    }
    int slot = weight_count++;
    weight_key[h] = x;
    weight_slot[h] = slot + 1;

    static int prefix[MAX_S + 1], suffix[MAX_S + 1];
    prefix[0] = 1;
    for (int i = 0; i < sample_count; ++i) {
        int factor = x - i;
        if (factor < 0) factor += MOD;
        prefix[i + 1] = static_cast<int>(static_cast<long long>(prefix[i]) * factor % MOD);
    }
    suffix[sample_count] = 1;
    for (int i = sample_count; i-- > 0;) {
        int factor = x - i;
        if (factor < 0) factor += MOD;
        suffix[i] = static_cast<int>(static_cast<long long>(suffix[i + 1]) * factor % MOD);
    }
    for (int i = 0; i < sample_count; ++i) {
        long long w = static_cast<long long>(prefix[i]) * suffix[i + 1] % MOD;
        w = w * invfac[i] % MOD * invfac[sample_count - 1 - i] % MOD;
        if ((sample_count - 1 - i) & 1) w = w ? MOD - w : 0;
        weights[slot][i] = static_cast<int>(w);
    }
    return weights[slot];
}

struct Segment {
    int right = INF;
    std::array<int, MAX_S> value{};

    int eval(int x) const {
        int field_x = x % MOD;
        if (field_x < sample_count) return value[field_x];
        const int *w = get_weights(x);
        u128 acc = 0;
        for (int i = 0; i < sample_count; ++i)
            acc += static_cast<unsigned long long>(value[i]) * static_cast<unsigned>(w[i]);
        return static_cast<int>(acc % MOD);
    }
};

struct Function {
    std::vector<Segment> seg;

    void reserve_range(int left, int right) {
        std::size_t ir = 0;
        while (seg[ir].right < right) ++ir;
        seg[ir].right = right;
        seg.resize(ir + 1);
        Segment zero;
        zero.right = INF;
        seg.push_back(std::move(zero));
        if (left == 1) return;
        std::size_t il = 0;
        while (seg[il].right < left) ++il;
        if (il) seg.erase(seg.begin(), seg.begin() + static_cast<long>(il));
        Segment lead;
        lead.right = left - 1;
        seg.insert(seg.begin(), std::move(lead));
    }

    void shrink() {
        std::size_t out = 0;
        int last = 0;
        for (std::size_t i = 0; i < seg.size(); ++i) {
            if (seg[i].right > last) {
                if (out != i) seg[out] = std::move(seg[i]);
                last = seg[out].right;
                ++out;
            }
        }
        seg.resize(out);
    }

    void prefix_sum() {
        int last_right = 0, carry = 0;
        for (Segment &s : seg) {
            int sum = 0;
            for (int i = 0; i < sample_count; ++i) {
                sum = add_mod(sum, s.value[i]);
                s.value[i] = sum;
            }
            int at_left = s.eval(last_right);
            int at_right = s.eval(s.right);
            int adjust = sub_mod(carry, at_left);
            for (int i = 0; i < sample_count; ++i) s.value[i] = add_mod(s.value[i], adjust);
            carry = add_mod(carry, sub_mod(at_right, at_left));
            last_right = s.right;
        }
    }
};

static Function cache[MAX_N + 1][MAX_N + 1];
static unsigned char visited[MAX_N + 1][MAX_N + 1];
static Function empty_function;

static Function add_functions(const Function &a, const Function &b) {
    Function out;
    out.seg.reserve(a.seg.size() + b.seg.size());
    std::size_t i = 0, j = 0;
    while (i < a.seg.size() && j < b.seg.size()) {
        Segment s;
        s.right = std::min(a.seg[i].right, b.seg[j].right);
        for (int k = 0; k < sample_count; ++k)
            s.value[k] = add_mod(a.seg[i].value[k], b.seg[j].value[k]);
        out.seg.push_back(std::move(s));
        if (a.seg[i].right == out.seg.back().right) ++i;
        if (b.seg[j].right == out.seg.back().right) ++j;
    }
    return out;
}

static Function multiply_functions(const Function &a, const Function &b) {
    Function out;
    out.seg.reserve(a.seg.size() + b.seg.size());
    std::size_t i = 0, j = 0;
    while (i < a.seg.size() && j < b.seg.size()) {
        Segment s;
        s.right = std::min(a.seg[i].right, b.seg[j].right);
        for (int k = 0; k < sample_count; ++k)
            s.value[k] = static_cast<int>(static_cast<long long>(a.seg[i].value[k]) * b.seg[j].value[k] % MOD);
        out.seg.push_back(std::move(s));
        if (a.seg[i].right == out.seg.back().right) ++i;
        if (b.seg[j].right == out.seg.back().right) ++j;
    }
    return out;
}

static Function shift_function(const Function &a) {
    Function out;
    out.seg.reserve(a.seg.size() + 1);
    Segment zero;
    zero.right = 1;
    out.seg.push_back(std::move(zero));
    const int *minus_one = get_weights(MOD - 1);
    for (const Segment &src : a.seg) {
        Segment s;
        s.right = src.right == INF ? INF : src.right + 1;
        u128 acc = 0;
        for (int i = 0; i < sample_count; ++i)
            acc += static_cast<unsigned long long>(src.value[i]) * static_cast<unsigned>(minus_one[i]);
        s.value[0] = static_cast<int>(acc % MOD);
        std::memcpy(s.value.data() + 1, src.value.data(),
                    static_cast<std::size_t>(sample_count - 1) * sizeof(int));
        out.seg.push_back(std::move(s));
    }
    return out;
}

static const Function &solve(int left, int right) {
    if (left > right) return empty_function;
    if (visited[left][right]) return cache[left][right];
    visited[left][right] = 1;
    Function result;
    bool first = true;
    for (int mid = left; mid <= right; ++mid) {
        if (std::abs((mid - left) - (right - mid)) > 2) continue;
        Function shifted = (mid == right) ? empty_function : shift_function(solve(mid + 1, right));
        Function term = multiply_functions(solve(left, mid - 1), shifted);
        term.reserve_range(low_bound[mid], high_bound[mid]);
        if (first) {
            result = std::move(term);
            first = false;
        } else {
            result = add_functions(result, term);
        }
    }
    result.shrink();
    result.prefix_sum();
    cache[left][right] = std::move(result);
    return cache[left][right];
}

static inline char *write_uint(char *out, unsigned x) {
    char tmp[16]; unsigned len = 0;
    do tmp[len++] = static_cast<char>('0' + x % 10), x /= 10; while (x);
    while (len) *out++ = tmp[--len];
    *out++ = '\n';
    return out;
}

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

int main(long argc, char **argv) {
#ifdef LOCAL
    (void)argc; (void)argv;
    static char local_in[8192], local_out[64];
    std::size_t local_size = std::fread(local_in, 1, sizeof local_in, stdin);
    DuckInfo local_info{};
    local_info.stdin_ptr = local_in; local_info.stdin_size = local_size;
    local_info.stdout_ptr = local_out; local_info.stdout_limit = sizeof local_out;
    DuckInfo *info = &local_info;
#else
    DuckInfo *info = duck_info(argc, argv);
#endif
    const char *in = info->stdin_ptr;
    n = static_cast<int>(read_uint(in));
    sample_count = n + 2;
    for (int i = 1; i <= n; ++i) {
        low_bound[i] = static_cast<int>(read_uint(in));
        high_bound[i] = static_cast<int>(read_uint(in));
    }

    int factorial = 1;
    for (int i = 1; i < sample_count; ++i) factorial = static_cast<int>(static_cast<long long>(factorial) * i % MOD);
    invfac[sample_count - 1] = mod_pow(factorial, MOD - 2);
    for (int i = sample_count - 1; i; --i)
        invfac[i - 1] = static_cast<int>(static_cast<long long>(invfac[i]) * i % MOD);

    Segment one;
    one.right = INF;
    for (int i = 0; i < sample_count; ++i) one.value[i] = 1;
    empty_function.seg.push_back(std::move(one));

    int answer = solve(1, n).seg.back().eval(INF);
    char *end = write_uint(info->stdout_ptr, static_cast<unsigned>(answer));
    info->stdout_size = static_cast<u64>(end - info->stdout_ptr);
#ifdef LOCAL
    std::fwrite(info->stdout_ptr, 1, info->stdout_size, stdout);
    return 0;
#else
    duck_exit();
#endif
}

评测结果