Submission #525610

#	Time	Username	Problem	Language	Result	Execution time	Memory
525610		ParsaEs	Ruins 3 (JOI20_ruins3)	C++17	100 / 100	390 ms	18716 KiB

ruins3

//InTheNameOfGOD
//PRS;)
#include<iostream>
#define Fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int xn = 2e3 + 5;
ll cnt[xn][xn], pr[xn][xn], dp[xn];
bool vis[xn << 1];
ll pp(ll x, ll y)
{
	if(y < 1) return 1;
	if(y < 2) return x;
	ll ret = pp(x, y / 2);
	ret = (ret * ret) % mod;
	if(y & 1) ret = (ret * x) % mod;
	return ret;
}
int main()
{
	Fast
	int n;
	cin >> n;
	for(int i = 0; i <= n; i++) cnt[0][i] = 1;
	for(int i = 1; i <= n; i++) for(int j = i; j <= n; j++)
		cnt[i][j] = (cnt[i - 1][j - 1] + cnt[i][j - 1]) % mod;
	pr[n * 2 + 1][0] = dp[0] = 1;
	for(ll i = 1; i <= n; i++) for(ll j = 1; j <= i; j++)
	{
		ll prs = (cnt[j - 1][i - 1] * dp[j - 1]) % mod;
		prs = (prs * dp[i - j]) % mod;
		prs = (prs * (i - j + 2)) % mod;
		dp[i] = (dp[i] + prs) % mod;
	}
	int n1 = n;
	while(n1--)
	{
		int x;
		cin >> x;
		vis[x] = 1;
	}
	ll a1 = 0, a2 = 0;
	for(int i = (n << 1); i > 0; i--)
	{
		if(!vis[i])
		{
			ll z = 0;
			for(int j = 0; j <= a2; j++) pr[i][j] = (pr[i + 1][j] * max(j - a1, z)) % mod;
			a1++;
			continue;
		}
		for(int j = 0; j < xn; j++) pr[i][j] = pr[i + 1][j];
		for(int j = 0; j <= a2 + 1; j++) for(int k = 1; k <= j; k++)
		{
			ll prs = (cnt[j - k][a2 - k + 1] * pr[i + 1][k - 1]) % mod;
			prs = (prs * dp[j - k]) % mod;
			prs = (prs * (j - k + 2)) % mod;
			pr[i][j] = (pr[i][j] + prs) % mod;
		}
		a2++;
	}
	ll ans = pp(pp(2, n), mod - 2);
	ans = (ans * pr[1][n]) % mod;
	return cout << ans << '\n', 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 52 / 52
• Subtask 3: 42 / 42