제출 #107720

#제출 시각아이디문제언어결과실행 시간메모리
107720MinnakhmetovBoat (APIO16_boat)C++14
100 / 100
651 ms6904 KiB
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define ll long long
#define ull unsigned long long
#define all(aaa) aaa.begin(), aaa.end()
#pragma warning(disable : 4996)

const int N = 505, MOD = 1e9 + 7, M = N * 2;;
int a[N], b[N], dp[N][M], dp2[M][N], c[N][N], c2[N];
int n;
vector<int> occ[M];

ll bp(ll a, ll p) {
	ll r = 1;
	while (p > 0) {
		if (p & 1)
			r = r * a % MOD;
		p >>= 1;
		a = a * a % MOD;
	}
	return r;
}

void f(int& a, int b) {
	a += b;
	if (a >= MOD)
		a -= MOD;
}



//const int M1 = 1e3 + 5, N1 = 10;
//int dpb[N1][M1];
//
//int slow() {
//	dpb[0][0] = 1;
//	int q = 0;
//	for (int i = 0; i < n; i++) {
//		for (int j = 0; j < M1; j++) {
//			f(dpb[i + 1][j], dpb[i][j]);
//		}
//		for (int j = 1; j < M1; j++) {
//			f(dpb[i][j], dpb[i][j - 1]);
//		}
//		for (int j = a[i]; j <= b[i]; j++) {
//			f(dpb[i + 1][j], dpb[i][j - 1]);
//		}
//	}
//
//	for (int j = 1; j < M1; j++) {
//		f(dpb[n][j], dpb[n][j - 1]);
//	}
//
//	return dpb[n][M1 - 1] - 1;
//}

signed main() {
#ifdef HOME
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);


	for (int i = 0; i < N; i++) {
		c[i][0] = 1;
	}

	for (int i = 1; i < N; i++) {
		for (int j = 1; j < N; j++) {
			c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
		}
	}


	cin >> n;
	
	vector<int> v;
	v.push_back(0);

	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
		v.push_back(a[i]);
		v.push_back(b[i] + 1);
	}

	sort(all(v));
	v.erase(unique(all(v)), v.end());

	int m = v.size() - 1;


	

	for (int i = 1; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (a[j] <= v[i] && b[j] >= v[i + 1] - 1) {
				occ[i].push_back(j);
			}
		}
	}

	for (int i = 1; i < m; i++) {
		ll t = 1;
		for (int j = 0; j <= n; j++) {
			c2[j] = t;
			t = t * (v[i + 1] - v[i] - j) % MOD * bp(j + 1, MOD - 2) % MOD;
		}
		for (int j = 1; j <= occ[i].size(); j++) {
			for (int h = 1; h <= j; h++) {
				dp2[i][j] = (dp2[i][j] + c[j - 1][h - 1] * (ll)c2[h]) % MOD;
			}
		}
	}

	
	dp[0][0] = 1;

	for (int i = 0; i < n; i++) {
		for (int j = 1; j < m; j++) {
			f(dp[i][j], dp[i][j - 1]);
			int g = lower_bound(all(occ[j]), i) - occ[j].begin();
			for (int k = g; k < occ[j].size(); k++) {
				dp[occ[j][k] + 1][j] = (dp[occ[j][k] + 1][j] + dp[i][j - 1] * (ll)dp2[j][k - g + 1]) % MOD;
			}
		}
	}


	int ans = 0;
	for (int i = 1; i < m; i++) {
		f(ans, dp[n][i]);
	}
	for (int i = 1; i < n; i++) {
		f(ans, dp[i][m - 1]);
	}
	cout << ans;

	/*cout << "\n" << slow() << "\n";*/
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

boat.cpp:42:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable : 4996)
 
boat.cpp: In function 'int main()':
boat.cpp:146:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 1; j <= occ[i].size(); j++) {
                   ~~^~~~~~~~~~~~~~~~
boat.cpp:160:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int k = g; k < occ[j].size(); k++) {
                    ~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...