제출 #673401

#제출 시각아이디문제언어결과실행 시간메모리
673401S2speedBoat (APIO16_boat)C++17
9 / 100
115 ms8428 KiB
#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize ("Ofast")

#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
typedef long long ll;

const ll maxn = 1e3 + 17 , md = 1e9 + 7;

ll tav(ll n , ll k){
	ll res = 1;
	while(k > 0){
		if(k & 1){
			res *= n; res %= md;
		}
		n *= n; n %= md;
		k >>= 1;
	}
	return res;
}

ll l[maxn] , r[maxn] , w[maxn] , f[maxn][maxn] , dp[maxn][maxn] , pd[maxn];
vector<ll> v;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	ll n;
	cin>>n;
	for(ll i = 0 ; i < n ; i++){
		cin>>l[i]>>r[i]; l[i]--;
		v.push_back(l[i]); v.push_back(r[i]);
	}
	sort(all(v));
	v.resize(distance(v.begin() , unique(all(v))));
	ll vs = sze(v);
	for(ll i = 0 ; i < vs - 1 ; i++){
		w[i] = v[i + 1] - v[i];
		ll lm = min(w[i] , n);
		for(ll j = 1 ; j <= lm ; j++){
			f[i][j] = (w[i] - j + 1) * tav(j , md - 2) % md;
		}
	}
	for(ll i = 0 ; i < n ; i++){
		l[i] = lower_bound(all(v) , l[i]) - v.begin();
		r[i] = lower_bound(all(v) , r[i]) - v.begin();
	}
	fill(pd , pd + vs - 1 , 1);
	for(ll i = 0 ; i < n ; i++){
		for(ll j = r[i] - 1 ; j >= l[i] ; j--){
			ll h = 0 , lm = min(i , w[j]);
			for(ll k = lm ; k > 1 ; k--){
				ll o = dp[j][k - 1] * f[j][k] % md;
				dp[j][k] += o; dp[j][k] -= (dp[j][k] <= md) * md;
				h += o;
			}
			dp[j][1] += pd[j]; dp[j][1] -= (dp[j][1] >= md) * md;
			h += pd[j];
			for(ll k = j + 1 ; k < vs ; k++){
				pd[k] += h; pd[k] %= md;
			}
		}
	}
	ll ans = pd[vs - 1];
	cout<<ans<<'\n';
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...