제출 #251462

#제출 시각아이디문제언어결과실행 시간메모리
251462atoizBoat (APIO16_boat)C++14
100 / 100
692 ms3692 KiB
/*input
2
1 2
2 3
*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>

using namespace std;
 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define FORA(i, a) for (auto &i : a)
#define FORB(i, a, b) for (int i = a; i >= b; --i)

const int MOD = 1000000007, MAXN = 507;
int add(int x, int y) { return x -= ((x += y) >= MOD ? MOD : 0); }
int sub(int x, int y) { return x += ((x -= y) < 0 ? MOD : 0); }
int mul(int x, int y) { return (int) ((long long) x * y % MOD); }
int getinv(int x, int m) { return (x == 1 ? 1 : m - (int) ((long long) m * getinv(m % x, x) / x)); }
int N, A[MAXN], B[MAXN], M;
int eval[MAXN * 2][MAXN], inv[MAXN], prefsum[MAXN * 2];
vector<int> vals, dp[MAXN * 2];

void addfunc(vector<int> &a, vector<int> b)
{
	a.resize(max(a.size(), b.size()));
	FOR(i, 0, int(min(a.size(), b.size())) - 1) a[i] = add(a[i], b[i]);
}

int evalat(vector<int> &a, int x)
{
	int ans = 0;
	FOR(i, 0, ((int) a.size()) - 1) ans = add(ans, mul(eval[x][i], a[i]));
	return ans;
}

vector<int> sumfunc(vector<int> &a)
{
	if (a.empty()) return a;
	vector<int> b = a;
	b.insert(b.begin(), 0);
	return b;
}

void addint(vector<int> &a, int x)
{
	if (not a.empty()) a[0] = add(a[0], x);
	else a.push_back(x);
}

void subint(vector<int> &a, int x)
{
	if (not a.empty()) a[0] = sub(a[0], x);
	else a.push_back(x ? MOD - x : x);
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N;
	FOR(i, 1, N) {
		cin >> A[i] >> B[i];
		--A[i];
		vals.push_back(A[i]);
		vals.push_back(B[i]);
	}
	vals.push_back(-1);
	sort(vals.begin(), vals.end());
	vals.erase(unique(vals.begin(), vals.end()), vals.end());
	FOR(i, 1, N) {
		A[i] = (int) (lower_bound(vals.begin(), vals.end(), A[i]) - vals.begin());
		B[i] = (int) (lower_bound(vals.begin(), vals.end(), B[i]) - vals.begin());
	}

	FOR(i, 1, N + 5) inv[i] = getinv(i, MOD);
	M = (int) vals.size() - 1;
	FOR(i, 1, M) {
		eval[i][0] = 1;
		FOR(j, 1, N + 5) eval[i][j] = mul(eval[i][j - 1], mul((vals[i] + j - 1) % MOD, inv[j]));
		// FOR(j, 1, N + 5) cout << vals[i] << ' ' << j << ": " << eval[i][j] << endl;
	}

	FOR(id, 1, N) {
		int l = A[id], r = B[id];
		// cout << l << ' ' << r << " - " << vals[l] << ' ' << vals[r] << endl;
		FOR(i, 1, r - 2) {
			vector<int> sumf = sumfunc(dp[i]);
			int cur = sub(evalat(sumf, i + 1), evalat(sumf, i));
			prefsum[i] = add(prefsum[i - 1], cur);
			// cout << vals[i] << ' ' << vals[i + 1] << ": " << cur << ' ' << dp[i].size() << endl;
		}
		// cout << "S" << endl;

		FORB(i, r - 1, l) {
			// cout << vals[i] << ' ' << vals[i + 1] << ": " << dp[i].size();
			vector<int> sumf = sumfunc(dp[i]);
			vector<int> vec = sumf;
			addint(vec, prefsum[i - 1]);
			subint(vec, evalat(sumf, i));
			addint(vec, 1);
			dp[i] = move(vec);
			// cout << " " << dp[i].size() << endl;
		}
	}

	// cout << " - " << endl;
	FOR(i, 1, M - 1) {
		vector<int> sumf = sumfunc(dp[i]);
		int cur = sub(evalat(sumf, i + 1), evalat(sumf, i));
		prefsum[i] = add(prefsum[i - 1], cur);
		// cout << vals[i] << ' ' << vals[i + 1] << ": " << cur << ' ' << dp[i].size() << endl;
	} 
	cout << prefsum[M - 1] << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...