Submission #624914

#	Time	Username	Problem	Language	Result	Execution time	Memory
624914		QwertyPi	Boat (APIO16_boat)	C++14	0 / 100	2 ms	852 KiB

boat

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 113;
const int M = 1e9 + 7;
int a[N], b[N];
int d[N * 2];
int dp[N][N * 2][N];

int n, m;

int pm(int a, int b){
	if(b == 0) return 1;
	return pm(a * a % M, b / 2) * (b % 2 ? a : 1) % M;
}

int mi(int a){
	return pm(a, M - 2);
}

int fact[N];
int C(int n, int r){
	if(n < r) return 0;
	return fact[n] * mi(fact[r]) % M * mi(fact[n - r]) % M;
}

int32_t main(){
	cin >> n;
	fact[0] = 1;
	for(int i = 1; i <= n; i++){
		fact[i] = (fact[i - 1] * i) % M;
	}
	for(int i = 0; i < n; i++){
		cin >> a[i] >> b[i];
	}
	vector<int> sp;
	sp.push_back(0);
	sp.push_back(1);
	for(int i = 0; i < n; i++){
		sp.push_back(a[i]);
		sp.push_back(b[i] + 1);
	}
	sort(sp.begin(), sp.end());
	sp.resize(unique(sp.begin(), sp.end()) - sp.begin());
	m = sp.size();
	{
		map<int, int> M;
		for(int i = 0; i < m; i++) M[sp[i]] = i;
		for(int i = 0; i < n; i++) a[i] = M[a[i]], b[i] = M[b[i] + 1];
	}
	for(int i = 0; i < m - 1; i++){
		d[i] = sp[i + 1] - sp[i];
	}
	dp[0][0][0] = 1;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			for(int k = 1; k <= n; k++){
				dp[i + 1][j][k] = dp[i][j][k];
			}
		}
		int s[m + 1] = {0};
		for(int j = 0; j < m; j++){
			for(int k = 0; k <= n; k++){
				s[j + 1] += dp[i][j][k];
			}
			s[j] %= M;
			s[j + 1] += s[j];
		}
		for(int j = a[i]; j < b[i]; j++){
			dp[i + 1][j][1] += s[j] * C(d[j], 1) % M * mi(C(d[j], 0)) % M;
			for(int k = 1; k < n; k++){
				dp[i + 1][j][k + 1] += dp[i][j][k] * C(d[j], k + 1) % M * mi(C(d[j], k)) % M;
			}
		}
		for(int j = 0; j < m; j++){
			for(int k = 1; k <= n; k++){
				dp[i + 1][j][k] %= M;
			}
		}
	}
	/*
	for(int i = 0; i <= n; i++){
		for(int j = 0; j < m; j++){
			for(int k = 0; k <= n; k++){
				cout << dp[i][j][k] << ' ';
			}
			cout << endl;
		}
		cout << endl;
	}
	*/
	int ans = 0;
	for(int i = 0; i <= n; i++){
		for(int j = 0; j < m; j++){
			for(int k = 1; k <= n; k++){
				ans += dp[i][j][k];
			}
		}
	}
	ans %= M;
	cout << ans << endl;
}

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