20pts求调
查看原帖
20pts求调
490978
小超手123楼主2024/3/15 11:07
#include<bits/stdc++.h>
#define int long long
#define N 3010
#define mod 1000000007
using namespace std;
int Pow(int a, int n) {
	if(n == 0) return 1;
	if(n == 1) return a;
	int x = Pow(a, n / 2);
	if(n % 2 == 0) return x * x % mod;
	else return x * x % mod * a % mod;
}
int inv(int x) {
	return Pow(x, mod - 2);
}
int n, ans;
struct node {
	int l, r;
}a[N];
int b[N], tot, c[N], len, L[N], R[N];
int h[N][N], fac[N], Inv[N], f[N][N], g[N][N];
int C(int j, int m) {
	return h[j][m - 1] * Inv[m - 1] % mod;
}
signed main() {
	//ios::sync_with_stdio(false);
	//cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> a[i].l >> a[i].r;
		b[++tot] = a[i].l;
		b[++tot] = a[i].r;
	}
	sort(b + 1, b + tot + 1);
	for(int i = 1; i <= tot; i++) 
		if(i == 1 || b[i] != b[i - 1]) c[++len] = b[i];
	//for(int i = 1; i <= len; i++) cout << c[i] << " ";
	//cout << endl;
	int H = 0;
	for(int i = 1; i < len; i++) {
		H++;
		L[H] = c[i];
		R[H] = c[i];
		if(c[i] + 1 <= c[i + 1] - 1) {
			H++;
			L[H] = c[i] + 1;
			R[H] = c[i + 1] - 1;
		}
	}
	H++;
	L[H] = c[len];
	R[H] = c[len];
	len = H;
	for(int i = 1; i <= len; i++) {
		//cout << L[i] << " " << R[i] << endl;
		h[i][0] = 1;
		int x = R[i] - L[i] + 1;
		for(int j = 1; j <= n; j++) h[i][j] = h[i][j - 1] * (x + j - 1) % mod;
	}
	fac[0] = Inv[0] = 1;
	for(int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
	Inv[n] = inv(fac[n]);
	for(int i = n - 1; i >= 1; i--) Inv[i] = Inv[i + 1] * (i + 1) % mod;
	f[0][0] = 1;
	for(int i = 0; i <= len; i++) g[0][i] = 1;
	//cout << C(1, 1) << " " << C(2, 1) << " " << C(3, 1) << endl;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= len; j++) { //枚举选什么
			g[i][j] = g[i][j - 1];
			if(a[i].l <= L[j] && R[j] <= a[i].r) ;
			else continue;
			int m = 0;
			for(int ll = i; ll >= 1; ll--) {
				if(a[ll].l <= L[j] && R[j] <= a[ll].r) m++;
				f[i][j] += g[ll - 1][j - 1] * C(j, m) % mod;
				f[i][j] %= mod;
				//if(i == n && j == 2) {
				//	cout << l << " : " << sum << " " << m << " " << sum * C(j, m) << endl;
				//}
			}
			ans = (ans + f[i][j]) % mod;
			g[i][j] = (g[i][j] + f[i][j]) % mod;
			//printf("f[%lld][%lld] = %lld\n", i, j, f[i][j]);
		}
	}
	cout << ans;
	return 0;
}
/*
5
114 514
12 13
100 120
231 333
13221 100000
*/
2024/3/15 11:07
加载中...