代码

#include <stdio.h>
#include <string.h>

const int MAXN = 305;
const int MAXH = 10005;

const int MOD = 1000000007;

int n;
int A[MAXN], B[MAXN];

struct data {
	int a[MAXH];
	
	data() {
		memset(a, 0, sizeof(a));
	}
	data(int x) {
		int a = A[x], b = B[x];
		for (int i = a; i <= b; i++) {
			this->a[i] = i - a + 1;
		}
		for (int i = b + 1; i < MAXH; i++) {
			this->a[i] = b - a + 1;
		}
	}
	
	void add(data *l, int mid, data *r) {
		int a = A[mid], b = B[mid];
		
		int sum = 0;
		for (int i = a; i <= b; i++) {
			sum = (sum + 1LL * l->a[i] * r->a[i - 1]) % MOD;
			this->a[i] = (this->a[i] + sum) % MOD;
		}
		
		for (int i = b + 1; i < MAXH; i++) {
			this->a[i] = (this->a[i] + sum) % MOD;
		}
	}
};

data *fs[MAXN][MAXN];
data *one;

void init() {
	one = new data();
	for (int i = 0; i < MAXH; i++) {
		one->a[i] = 1;
	}
}

inline int abs(int x) {
	return x < 0 ? -x : x;
}

data *solve(int l, int r) {
	if (l > r) return one;
	if (fs[l][r]) return fs[l][r];
	if (l == r) {
		fs[l][r] = new data(l);
		return fs[l][r];
	}
	
	data *ret = new data();
	
	for (int mid = (l + r) / 2 - 3; mid <= (l + r) / 2 + 3; mid++) {
		if (mid < l || mid > r) continue;
		if (abs((mid - l) - (r - mid)) > 2) continue;
		ret->add(solve(l, mid - 1), mid, solve(mid + 1, r));
	}
	
	return fs[l][r] = ret;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d%d", A + i, B + i);
	}
	
	init();
	data *f = solve(1, n);
	printf("%d\n", f->a[MAXH - 1]);
}

评测结果