Submission #795946

#TimeUsernameProblemLanguageResultExecution timeMemory
795946baneBoat (APIO16_boat)C++17
9 / 100
677 ms15632 KiB
#include<bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

/*
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/


#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
#define rep1n(i, n) for (int i = 1; i <= (n); ++i)
#define repr(i, n) for (int i = (n) - 1; i >= 0; --i)


#define fr first
#define sc second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define endl '\n'

 
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
 
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pair<int, int>>;
using vvi = vector<vi>;

const int nax = (int)501;
const int mod = (int)1e9 + 7;

int a[nax], b[nax];

ll bpow(ll a, ll b){
	ll res = 1;
	while(b){
		if (b & 1)
			res = (a * res) % mod;
		b /= 2;
		a = (a * a) % mod;
	}
	return res;
}


ll O = bpow(2,mod - 2);

ll c (ll a){
	return (((a * (a - 1))%mod) * O)%mod;
}

void solve(){
	int n;
	cin >> n;
	vector<int>pts;	
	rep1n(i,n){
		cin >> a[i] >> b[i];
		pts.pb(a[i]);
		pts.pb(b[i]);
		pts.pb(b[i] + 1);
	}
	pts.push_back(0);
	sort(all(pts));
	pts.erase(unique(all(pts)), pts.end());
	int m = pts.size();
	ll dp[n + 1][m + 1];
	memset(dp, 0LL, sizeof(dp));
	dp[0][0] = 1;
	ll choose[m + 1][n + 1];
	ll inv[m + 1][n + 1];
	rep(i,m - 1){
		choose[i][1] = pts[i + 1] - pts[i]; 
		for(int j = 2; j <= n; j++){
			choose[i][j] = (choose[i][j - 1] * bpow(j, mod - 2) % mod) * (pts[i + 1] - pts[i] - j + 1) % mod;
		}
		rep1n(j,n){
			inv[i][j] = bpow(choose[i][j], mod - 2);
		}
	}
	ll orz[m + 1];
	memset(orz, 0, sizeof(orz));
	rep1n(i,n){
		rep(j,m){
			dp[i][j] = dp[i - 1][j];
			//cout << dp[i][j] << " ";
		}
		cout << endl;
		rep(j,m - 1){
			if (a[i] <= pts[j] && pts[j + 1] <= b[i] + 1){
				//in range [L, R)
				if (orz[j]){
					dp[i][j] += (dp[i - 1][j] * inv[j][orz[j]] % mod) * choose[j][orz[j] + 1] % mod;
					dp[i][j] %= mod;
				}
				orz[j]++;
				repr(k,j){
					//dp[i-1][k]
					dp[i][j] += dp[i - 1][k] * (pts[j + 1] - pts[j]) % mod;
					dp[i][j] %= mod;
				}
			}
		}
	}
	
	ll ans = 0;
	rep1n(i,m-1){
		//cout << dp[n][i] << endl;
		ans += dp[n][i];
		ans %= mod;
	}
	cout << ans << '\n';
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);	
	int tt = 1;
	//cin >> tt;
	while(tt--){
		solve();
	}
	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...