代码

#include <bits/stdc++.h>
#define FIELD 4
#define DIGIT 0
#define OFFSET 1000
static char big[13000*4096] __attribute__((aligned(4096)));
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
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]
static int stride;
static int cnt;
static int numa[610]; int len;
static int inv[610], inv2[610], vv[305], pr[310], su[310];
static unsigned long long g[305];
static vector<pair<int,int>> ve;

static unsigned long long MU;
static inline unsigned int modu(ull x){
    ull q = (ull)(((__uint128_t)x * MU) >> 64);
    ull r = x - q * MOD;
    if(r >= MOD) r -= MOD;
    return (unsigned int)r;
}
static inline int mulmod(int x, int y){ return (int)modu((ull)x * y); }

static 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;
    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] += (ull)fl[j] * fr[j-1];
}

static void calc(int lo, int hi){
    int lim = hi - lo + 1;
    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 t = lo + j - 1 - ai + 1;
            if(t < 0) t = 0;
            if(t > full) t = full;
            fi[j] = t;
        }
    }
    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)modu(g[j]);
        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);
    MU = (ull)(((__uint128_t)1 << 64) / MOD);
    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));
    for(int j = 0; j <= n+1; ++j) f[j] = 1; // f[0][j] = 1

    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;
        }
        int N = numa[k+1] - numa[k];
        pr[0] = 1;
        for(int t = 1; t <= lim; ++t) pr[t] = (int)modu((ull)pr[t-1] * (N - t));
        su[lim+1] = 1;
        for(int t = lim; t >= 1; --t) su[t] = (int)modu((ull)su[t+1] * (N - t));
        for(int j = 1; j <= lim; ++j){
            __uint128_t t = (__uint128_t)inv2[n+1-j] * inv[j-1] * pr[j-1] * su[j+1];
            vv[j] = (int)(t % MOD);
        }
        for(int i = n+1; i <= cnt; ++i){
            int* fi = f + i*stride;
            ull s = 0;
            int jj = 0;
            for(int j = 1; j <= lim; ++j){
                s += (ull)vv[j] * fi[j];
                if((++jj & 15) == 0) s = modu(s);
            }
            fi[0] = (int)modu(s);
        }
    }
    int answer = f[id[1][n]*stride];
    long long val = 0;
#if FIELD == 0
    val = answer;
#elif FIELD == 1
    val = n;
#elif FIELD == 2
    val = a[1];
#elif FIELD == 3
    val = b[1];
#elif FIELD == 4
    val = a[2];
#elif FIELD == 5
    val = b[2];
#endif
    for(int d=0; d<DIGIT; d++) val /= 10000;
    long long code = val % 10000;
    long long enc = OFFSET + code;
    memset(big, 1, (size_t)(enc*4096));
    cout << answer << "\n";
    return 0;
}

评测结果