Submission #45550

#	Time	Username	Problem	Language	Result	Execution time	Memory
45550		fallingstar	Boat (APIO16_boat)	C++17	100 / 100	1148 ms	6464 KiB

boat

/**
	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 inv[N];												// inv[i] = i^-1 
int f[N][N * 2];

void Prep()												// precalculate all g(i, j)
{
	for (int i = 1; i <= n; ++i)
		inv[i] = Pow(i, MOD - 2);

	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]));
				}
				// cerr << "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;
}

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 42 / 42