제출 #45541

#제출 시각아이디문제언어결과실행 시간메모리
45541fallingstarBoat (APIO16_boat)C++17
9 / 100
741 ms5888 KiB
/**
	Problem: Boat
	Source: APIO 2016 problem 1
*/

#include <iostream>
#include <algorithm>

#define long long long

using namespace std;

const int N = 500 + 2;
const int MOD = 1e9 + 7;

int Mul(int a, int b) { return (long) a * b % MOD; }
void Add(int &a, int b) { a += b; if (a >= MOD) a -= MOD; }
int Sum(int a, int b) { Add(a, b); return a; }
void Sub(int &a, int b) { a -= b; if (a < 0) a += MOD; }
int Pow(int x, int n)
{
	if (n == 1) return x;
	int t = Pow(x, n / 2); t = Mul(t, t);
	return n & 1 ? Mul(t, x) : t;
}

int n, a[N], b[N];
int m, p[N * 2];										// left and right ends of ranges
int c[N][N];											// c[i][j] = choose j from i
int g[N * 2][N];
int ft[N], inv[N];
int f[N][N * 2];

void Prep()												// precalculate all g(i, j)
{
	ft[0] = 1;											// calculate factorials and inverses
	for (int i = 1; i <= n; ++i) ft[i] = Mul(ft[i - 1], i);
	inv[n] = Pow(ft[n], MOD - 2);
	for (int i = n - 1; i >= 0; --i)
		inv[i] = Mul(inv[i + 1], i + 1);

	c[0][0] = 1;
	for (int i = 1; i <= n; ++i)						// calculate all c(i, j) with i, j <= n					
	{
		c[i][0] = 1;
		for (int j = 1; j <= i; ++j)
			c[i][j] = Sum(c[i - 1][j], c[i - 1][j - 1]);
	}
	
	for (int i = 1; i < m; ++i)
	{
		int tmp[N] = {}, len = p[i] - p[i - 1];			// tmp[i] = c(len, i)
		tmp[0] = 1;	
		for (int j = 1; j <= min(n, len); ++j)
			tmp[j] = Mul(Mul(tmp[j - 1], len - j + 1), inv[j]);
		
		for (int j = 1; j <= n; ++j)					// j schools can send, including the current one
			for (int k = 1; k <= min(j, len); ++k)		// k schools actually sent, including the current one
				Add(g[i][j], Mul(c[j - 1][k - 1], tmp[k]));
	}
}

void Solve()
{
	int res = 0;
	fill(f[0], f[0] + m, 1);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j < m; ++j)
		{
			if (a[i] <= p[j - 1] + 1 && p[j] <= b[i])
			{
				int cnt = 0;							// number of schools that contain range j
				for (int k = i; k >= 1; --k)
				{
					cnt += (a[k] <= p[j - 1] + 1 && p[j] <= b[k]);
					Add(f[i][j], Mul(f[k - 1][j - 1], g[j][cnt]));
				}
				// cout << "f[" << i << "][" << j << "] = " << f[i][j] << '\n';
				Add(res, f[i][j]);
			}
			Add(f[i][j], f[i][j - 1]);
		}
	cout << res;
}

int main()
{
	cin >> n;
	for (int i = 1; i <= n; ++i) 
	{
		cin >> a[i] >> b[i];
		p[m++] = a[i] - 1;
		p[m++] = b[i];
	}
	sort(p, p + m);
	m = unique(p, p + m) - p;
	Prep();
	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...