제출 #1359727

#제출 시각아이디문제언어결과실행 시간메모리
1359727blackscreen1Boat (APIO16_boat)C++20
36 / 100
277 ms17472 KiB
#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_multiset;
#define ll long long
#define iloop(m, h) for (auto i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define lloop(m, h) for (auto l = m; l != h; l += (m < h ? 1 : -1))
#define pll pair<ll, ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
ll n, m, prv = 0, dp[1005][1005], dp2[1005][1005], cr, sz[1005], invd[1005];
ll c[1005][1005];
pll a[505], b[505];
set<ll> st;
vector<pll> rngs;
vector<ll> cs;
ll expo(ll a, ll b, ll m) {
	ll res = 1;
	a %= m;
	while (b) {
		if (b&1) res = (res*a) % m;
		a = (a*a) % m;
		b >>= 1;
	}
	return res;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	iloop(0, n) {
		cin >> a[i].first >> a[i].second;
		st.insert(a[i].first);
		st.insert(a[i].second);
	}
	iloop(1, n+1) invd[i] = expo(i, MOD1-2, MOD1);
	for (auto it : st) {
		if (prv && prv+1 < it) rngs.push_back({prv+1, it-1}), cs.push_back(prv+1);
		rngs.push_back({it, it}), cs.push_back(it);
		prv = it;
	}
	m = rngs.size();
	iloop(0, m) {
		sz[i] = rngs[i].second - rngs[i].first + 1;
		jloop(1, n+1) {
			if (j == 1) c[i][j] = sz[i];
			else c[i][j] = (((c[i][j-1]*(sz[i] + j - 1))%MOD1)*invd[j])%MOD1;
			// c[i][j] = sz[j] + i - 1 choose i
		}
	}
	iloop(0, n) {
		b[i].first = lower_bound(cs.begin(), cs.end(), a[i].first) - cs.begin();
		b[i].second = upper_bound(cs.begin(), cs.end(), a[i].second) - cs.begin() - 1;
	}
	iloop(0, n) {
		jloop(0, m) dp[i][j] = 0;
		jloop(b[i].second, b[i].first-1) {
			cr = 1;
			kloop(i-1, -1) {
				if (j) dp[i][j] += dp2[k][j-1] * c[j][cr];
				if (b[k].first <= j && b[k].second >= j) cr++;
				dp[i][j] %= MOD1;
			}
			dp[i][j] += c[j][cr];
			dp[i][j] %= MOD1;
		}
		jloop(0, m) dp2[i][j] = (dp[i][j] + (j ? dp2[i][j-1] : 0))%MOD1;
	}
	ll cans = 0;
	iloop(0, n) jloop(0, m) {cans += dp[i][j]; cans %= MOD1;}
	cout << cans;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…