代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;

static int n;
static int a[305], b[305];
static int id[305][305];
static int L[46000], R[46000];
static int *f;           // flat: f[i*stride + j], i in [0..cnt], j in [0..n+1]
static int stride;
static int cnt;
static int numa[610]; int len;
static int inv[610], inv2[610], vv[305];
static unsigned long long g[305];
static vector<pair<int,int>> ve;

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

static void dfs(int l, int r){
    if(l > r) return;
    if(l == r){ id[l][r] = l; return; }
    if(id[l][r]) return;
    id[l][r] = -1;  // temp visited marker (nonzero)
    ve.push_back({l, r});
    for(int m = l; m <= r; ++m){
        if(abs(2*m - l - r) <= 2){ dfs(l, m-1); dfs(m+1, r); }
    }
}

static inline void add_center(int l2, int r2, int mid, int lo, int lim){
    int lid = (mid-1 >= l2) ? id[l2][mid-1] : 0;
    int rid = (mid+1 <= r2) ? id[mid+1][r2] : 0;
    int* fl = f + lid*stride;
    int* fr = f + rid*stride;
    int jlo = max(1, a[mid] - lo + 1);
    int jhi = min(b[mid] - lo + 1, lim);
    for(int j = jlo; j <= jhi; ++j) g[j] += (unsigned long long)fl[j] * fr[j-1];
}

static void calc(int lo, int hi){
    int lim = hi - lo + 1;
    // base: single positions
    for(int i = 1; i <= n; ++i){
        int* fi = f + i*stride;
        int ai = a[i], bi = b[i];
        int full = bi - ai + 1;
        for(int j = 1; j <= lim; ++j){
            int h = lo + j - 1;
            int t = h - ai + 1;
            if(t < 0) t = 0;
            if(t > full) t = full;
            fi[j] = t;
        }
    }
    // composite intervals, shortest to longest
    for(int i = cnt; i > n; --i){
        int* fi = f + i*stride;
        int l2 = L[i], r2 = R[i];
        for(int j = 1; j <= lim; ++j) g[j] = 0;
        if((r2 - l2 + 1) & 1){
            int mid = (l2 + r2 - 2) / 2;
            add_center(l2, r2, mid, lo, lim);
            add_center(l2, r2, mid+1, lo, lim);
            add_center(l2, r2, mid+2, lo, lim);
        } else {
            int mid = (l2 + r2 - 1) / 2;
            add_center(l2, r2, mid, lo, lim);
            add_center(l2, r2, mid+1, lo, lim);
        }
        for(int j = 1; j <= lim; ++j) fi[j] = (int)(g[j] % MOD);
        for(int j = 1; j <= lim; ++j){ int t = fi[j] + fi[j-1]; if(t >= MOD) t -= MOD; fi[j] = t; }
    }
    for(int i = 1; i <= cnt; ++i) f[i*stride] = f[i*stride + lim];
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for(int i = 1; i <= n; ++i){ cin >> a[i] >> b[i]; numa[++len] = a[i]; numa[++len] = b[i]+1; }

    dfs(1, n);
    sort(ve.begin(), ve.end(), [](const pair<int,int>&p, const pair<int,int>&q){ return p.second-p.first > q.second-q.first; });
    cnt = n;
    for(auto& p : ve){ id[p.first][p.second] = ++cnt; L[cnt] = p.first; R[cnt] = p.second; }

    stride = n + 2;
    f = (int*)calloc((size_t)(cnt+1) * stride, sizeof(int));

    // empty interval = 1 for all offsets
    for(int j = 0; j <= n+1; ++j) f[j] = 1; // f[0][j] = 1

    // factorials
    inv[0] = 1;
    for(int i = 1; i <= 600; ++i) inv[i] = (ll)inv[i-1]*i % MOD;
    inv[600] = power(inv[600], MOD-2);
    for(int i = 599; i >= 1; --i) inv[i] = (ll)inv[i+1]*(i+1) % MOD;
    memcpy(inv2, inv, sizeof(inv));
    for(int i = 1; i <= 600; ++i) if(i & 1) inv2[i] = (MOD - inv2[i]) % MOD;

    sort(numa+1, numa+1+len);
    len = unique(numa+1, numa+1+len) - numa - 1;
    int lim = n + 1;
    for(int k = 1; k < len; ++k){
        int seg = numa[k+1] - numa[k];
        if(seg <= lim){ calc(numa[k], numa[k+1]-1); continue; }
        calc(numa[k], numa[k] + lim - 1);
        for(int i = 1; i <= n; ++i){
            int t = numa[k+1] - a[i];
            if(t < 0) t = 0;
            int full = b[i] - a[i] + 1;
            if(t > full) t = full;
            f[i*stride] = t;
        }
        ll all = 1;
        for(int j = 1; j <= lim; ++j) all = all * (numa[k+1] - numa[k] - j) % MOD;
        for(int j = 1; j <= lim; ++j){
            vv[j] = all * (ll)inv2[n+1-j] % MOD * inv[j-1] % MOD * power(numa[k+1]-numa[k]-j, MOD-2) % MOD;
        }
        for(int i = n+1; i <= cnt; ++i){
            int* fi = f + i*stride;
            ll s = 0;
            for(int j = 1; j <= lim; ++j) s += (ll)vv[j] * fi[j] % MOD;
            fi[0] = s % MOD;
        }
    }
    cout << f[id[1][n]*stride] << "\n";
    return 0;
}

评测结果