Submission #246028

#	Time	Username	Problem	Language	Result	Execution time	Memory
246028		wwdd	Boat (APIO16_boat)	C++14	100 / 100	614 ms	12664 KiB

boat

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MN = 510;
const ll M = 1e9+7;
ll dp[2][MN*2][MN];
ll cof[MN*2][MN];
ll nv[MN],sz[2*MN];
inline ll mul(ll a, ll b) {return (a*b)%M;}
ll bp(ll b, ll p) {
	ll ac = 1;
	while(p) {
		if(p&1) {ac = mul(ac,b);}
		b = mul(b,b);
		p >>= 1;
	}
	return ac;
}
ll inv(ll v) {return bp(v,M-2);}
void pre(int pct, int n) {
	for(int i=1;i<=n+1;i++) {
		nv[i] = inv(i);
	}
	for(int i=0;i<pct-1;i++) {
		cof[i][0] = sz[i];
	}
	for(int i=1;i<=n;i++) {
		for(int j=0;j<pct-1;j++) {
			cof[j][i] = mul(cof[j][i-1],mul(sz[j]-i,nv[i+1]));
		}
	}
}
ll st[MN],ed[MN];
int main() {
	ll n;
	cin >> n;
	map<ll,ll> bo;
	for(int i=0;i<n;i++) {
		cin >> st[i] >> ed[i];
		bo[st[i]] = -1;
		bo[ed[i]+1] = -1;
	}
	int pct = 0;
	ll ls = -1;
	for(auto& it: bo) {
		it.second = pct;
		if(pct > 0) {
			sz[pct-1] = it.first-ls;
		}
		ls = it.first;
		pct++;
	}
	for(int i=0;i<n;i++) {
		st[i] = bo[st[i]];
		ed[i] = bo[ed[i]+1];
	}
	pre(pct, n);
	int cu = 0;
	memset(dp,0,sizeof(dp));
	for(int i=0;i<n;i++) {
		int nu = 1-cu;
		for(int j=0;j<pct-1;j++) {
			for(int k=0;k<=i;k++) {
				dp[nu][j][k] = dp[cu][j][k];
			}
		}
		ll rs = 1;
		for(int j=0;j<st[i];j++) {
			for(int k=0;k<=i;k++) {
				rs += mul(dp[cu][j][k],cof[j][k]);
				if(rs >= M) {rs -= M;}
			}
		}
		for(int j=st[i];j<ed[i];j++) {
			dp[nu][j][0] += rs;
			if(dp[nu][j][0] >= M) {dp[nu][j][0] -= M;}
			for(int k=0;k<=i;k++) {
				dp[nu][j][k+1] += dp[cu][j][k];
				if(dp[nu][j][k+1] >= M) {
					dp[nu][j][k+1] -= M;
				}
				rs += mul(dp[cu][j][k],cof[j][k]);
				if(rs >= M) {rs -= M;}
			}
		}
		cu = nu;
	}
	ll res = 0;
	for(int i=0;i<pct-1;i++) {
		for(int j=0;j<=n;j++) {
			res += mul(dp[cu][i][j],cof[i][j]);
		}
	}
	res %= M;
	cout << res << '\n';
}

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