Submission #526609

#	Time	Username	Problem	Language	Result	Execution time	Memory
526609		Arnch	Ruins 3 (JOI20_ruins3)	C++17	100 / 100	556 ms	9344 KiB

ruins3

// oooo
/*
 be hengam shena mesle y dasto pa cholofti ~
 bepa to masire dahane koose neyofti ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()

const ll inf = 1e18, N = 2000, mod = 1e9 + 7, pr = 1000696969;

int a[N];
ll dp[N], sf[N][N];
ll fac[N], rfac[N];
bool mark[N];

ll poww(ll x, ll y) {
	ll res = 1;
	for(; y; y /= 2, x = x * x % mod)
		if(y & 1) {
			res = res * x % mod;
		}
	return res;
}

void pre() {
	fac[0] = 1;
	for(int i = 1; i < N; i++) fac[i] = fac[i - 1] * i % mod;
	for(int i = 0; i < N; i++) rfac[i] = poww(fac[i], mod - 2);
}

ll choose(ll x, ll y) {
	if(x > y) return 0;
	if(x == y) return 1;
	ll ans = fac[y];
	ans *= rfac[x];
	ans %= mod;
	ans *= rfac[y - x];
	ans %= mod;
	return ans;
}

int main() {
    ios :: sync_with_stdio(0), cin.tie(0);

	pre();
	
	int n; cin >>n;
	for(int i = 1; i <= n; i++) cin >>a[i], mark[a[i]] = 1;
	
	dp[0] = 1;
	for(int len = 1; len <= n; len++) {
		for(int j = 0; j < len; j++) {
			ll val = dp[j] * dp[len - j - 1];
			val %= mod;
			val *= choose(j, len - 1);
			val %= mod;
			val *= j + 2; val %= mod;
			dp[len] += val;
			dp[len] %= mod;
		}
	}

	int c0 = 0, c1 = 0;
	
	
	sf[2 * n + 1][0] = 1;
	for(int i = 2 * n; i > 0; i--) {
		if(mark[i] == 0) {
			for(int R = 0; R <= c1; R++) {
				sf[i][R] = sf[i + 1][R] * (max(0, R - c0));	
				sf[i][R] %= mod;
			}
			c0++;
			continue;
		}
		for(int R = 0; R <= c1 + 1; R++) {
			int k = c1 - R + 1;
			sf[i][R] = sf[i + 1][R];
			sf[i][R] %= mod;
			for(int j = 0; j < R; j++) {
				ll val = dp[j] * sf[i + 1][R - j - 1];
				val %= mod;
				val *= choose(j, c1 - (R - j) + 1);
				val %= mod;
				val *= j + 2;
				val %= mod;
				sf[i][R] += val;
				sf[i][R] %= mod;
			}
		}
		c1++;
	}
	
	ll ans = sf[1][n];
	ans *= poww(poww(2, n), mod - 2);
	ans %= mod;

	cout<<ans;

	
    return 0;
}

Compilation message (stderr)

ruins3.cpp: In function 'int main()':
ruins3.cpp:88:8: warning: unused variable 'k' [-Wunused-variable]
   88 |    int k = c1 - R + 1;
      |        ^

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