代码

#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, B = y; i <= B; i ++)
#define ff(i, x, y) for(int i = x, B = y; i <  B; i ++)
#define fd(i, x, y) for(int i = x, B = y; i >= B; i --)
#define ll long long
#define pp printf
#define hh pp("\n")
using namespace std;

const int N = 605;

int n, a[N], b[N], c[N], c0;
int bz[N][N], bz0;
int cnt;

const int mo = 1e9 + 7;

ll ksm(ll x, ll y) {
	ll s = 1;
	for(; y; y /= 2, x = x * x % mo)
		if(y & 1) s = s * x % mo;
	return s;
}

ll fac[N], nf[N], nf2[N];

void build(int n) {
	fac[0] = nf[0] = nf2[0] = 1;
	fo(i, 1, n) fac[i] = fac[i - 1] * i % mo;
	fo(i, 1, n) {
		nf[i] = ksm(fac[i], mo - 2);
		nf2[i] = ksm(i & 1 ? mo - fac[i] : fac[i], mo - 2);
	}
}

vector<int> d[1900][610];

ll p[N], q[N], p1[N], q1[N];

ll cz(ll x, int n) {
	fo(i, 0, n) {
		p1[i] = (!i ? 1 : p1[i - 1]) * (x - p[i]) % mo;
	}
	fd(i, n, 0) {
		q1[i] = (i == n ? 1 : q1[i + 1]) * (x - p[i]) % mo;
	}
	ll ans = 0;
	fo(i, 0, n) if(q[i]) {
		ans = (ans + q[i] * (!i ? 1 : p1[i - 1]) % mo * (i == n ? 1 : q1[i + 1]) % mo * nf[i] % mo * nf2[n - i]) % mo;
	}
	return ans;
}

ll query(int l, int r, int x, int w) {
	if(l > r) return 1;
	if(l == r) return max(0, min(x, b[l]) - a[l] + 1);
	int num = bz[l][r];
	if(x - c[w] <= r - l + 1) return d[num][w][x - c[w]];
	fo(i, 0, r - l + 1)	p[i] = c[w] + i, q[i] = d[num][w][i];
	return cz(x, r - l + 1);
}

void dg(int x, int y) {
	if(x >= y) return;
	if(bz[x][y]) return;
	bz[x][y] = ++ bz0;
	int num = bz[x][y];
	fo(i, x, y)	if(abs(i - x - (y - i)) <= 2) {
		dg(x, i - 1); dg(i + 1, y);
	}
	fo(j, 1, c0 - 1) {
		int mx = min(y - x + 1, c[j + 1] - c[j] - 1);
		d[num][j].resize(mx + 1);
		ll sum = (j == 1 ? 0 : query(x, y, c[j] - 1, j - 1));
		fo(k, 0, mx) {
			int mi = x + y >> 1;
			fo(i, max(x, mi - 1), min(y, mi + 1)) if(abs(i - x - (y - i)) <= 2) {
				if(c[j] + k >= a[i] && c[j] + k <= b[i])
					sum = (sum + query(x, i - 1, c[j] + k, j) * query(i + 1, y, c[j] + k - 1, j + (!k ? -1 : 0))) % mo;
			}
			d[num][j][k] = sum;
		}
	}
}

int main() {
	freopen("robot.in", "r", stdin);
	freopen("robot.out", "w", stdout);
	build(301);
	scanf("%d", &n);
	c[++ c0] = 0; c[++ c0] = 1e9 + 1;
	fo(i, 1, n) scanf("%d %d", &a[i], &b[i]), c[++ c0] = a[i], c[++ c0] = b[i];
	sort(c + 1, c + c0 + 1);
	c0 = unique(c + 1, c + c0 + 1) - (c + 1);
	dg(1, n);
	pp("%lld\n", (query(1, n, 1e9, c0 - 1) + mo) % mo);
}

评测结果