Submission #1319355

#TimeUsernameProblemLanguageResultExecution timeMemory
1319355nguyenkhangninh99Boat (APIO16_boat)C++20
0 / 100
446 ms6364 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e3 + 5, mod = 1e9 + 7;
int dp[maxn][maxn], pre[maxn][maxn],sum_dp[maxn],val[2*maxn],L[maxn],R[maxn],inv[maxn];
int binpow(int a, int b){
	int res = 1;
	while(b){
		if(b & 1) res  =res * a % mod;
		a = a * a % mod;
		b /= 2;
	}
	return res;
}
signed main(){
	ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
 //   freopen("BOAT.inp", "r", stdin);
   // freopen("BOAT.out", "w", stdout);
	int n; cin >> n;
	int cnt = 0;
	for(int i = 1; i <= n; i++){
		cin >> L[i] >> R[i];
		val[++cnt] = L[i];
		val[++cnt] = R[i] + 1;
	}
	sort(val + 1, val + cnt + 1);
	cnt = unique(val + 1, val + cnt + 1) - (val + 1);
	for(int i = 1; i <= n; i++) inv[i] = binpow(i, mod - 2);
	for(int i = 0; i <= cnt; i++) sum_dp[i] = 1;

	for(int i = 1; i <= n; i++){
		int idl = lower_bound(val + 1, val + cnt + 1, L[i]) - val;
		int idr = lower_bound(val + 1, val + cnt + 1, R[i] + 1) - val;
		
		for(int j = idl; j < idr; j++)
			for(int k = 1; k <= i; k++) pre[j][k] = dp[j][k];

		for(int j = idl; j < idr; j++){
			int len = (val[j + 1] - val[j]);
			dp[j][1] = (dp[j][1] + sum_dp[j-1] * len) % mod; //k = 1
			for(int k = 2; k <= i; k++){ //k > 1
				dp[j][k] = (dp[j][k] + pre[j][k - 1] * (len - k + 1) % mod * inv[k] % mod) % mod;
			}
		}

		for(int j = 1; j < cnt; j++){
            sum_dp[j] = sum_dp[j - 1] + 1;
			for(int k = 1; k <= i; k++) sum_dp[j] = (sum_dp[j] + dp[j][k]) % mod;
		}
	}

	int ans = 0;
	for(int j = 1; j < cnt; j++){
		for(int k = 1; k <= n; k++) ans = (ans + dp[j][k]) % mod;
    }
	cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...