Submission #524572

#	Time	Username	Problem	Language	Result	Execution time	Memory
524572		sare	Ruins 3 (JOI20_ruins3)	C++17	100 / 100	276 ms	11724 KiB

ruins3

//In the name of Allah :)
#include <bits/stdc++.h>
using namespace std;
string to_string(char c) { return string(1,c); }
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(const char* s) { return (string)s; }
string to_string(string s) { return s; }
template<class A> string to_string(complex<A> c) { 
	stringstream ss; ss << c; return ss.str(); }
string to_string(vector<bool> v) { 
	string res = "{"; for(int i = 0; i < (int)v.size(); i++) res += char('0'+v[i]);
	res += "}"; return res; }
template<size_t SZ> string to_string(bitset<SZ> b) {
	string res = ""; for(size_t i = 0; i < SZ; i++) res += char('0'+b[i]);
	return res; }
template<class A, class B> string to_string(pair<A,B> p);
template<class T> string to_string(T v) { // containers with begin(), end()
	bool fst = 1; string res = "{";
	for (const auto& x: v) {
		if (!fst) res += ", ";
		fst = 0; res += to_string(x);
	}
	res += "}"; return res;
}
template<class A, class B> string to_string(pair<A,B> p) {
	return "("+to_string(p.first)+", "+to_string(p.second)+")"; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
	cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
	DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define wis(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "] : [", DBG(__VA_ARGS__)
#else
#define wis(...) 0
#endif
typedef long long ll;
#define all(x) (x).begin(), (x).end()
const int MAXN = 1210, MOD = 1e9 + 7;
int dp[MAXN], pre[MAXN][MAXN], comb[MAXN][MAXN];
bool rem[2 * MAXN];

inline int power (ll a, ll b) {
	ll res = 1;
	for (; b; b >>= 1, a = (a * a) % MOD) {
		if (b & 1) {
			res = (res * a) % MOD;
		}
	}
	return res;
}
inline int inv (int x) {
	return power(x, MOD - 2);
}

inline void add (int& a, const int& b) {
	a += b;
	if (a >= MOD) {
		a -= MOD;
	}
}

int main() {
	ios::sync_with_stdio(0);
#ifndef LOCAL
	cin.tie(0);
#endif
	for (int i = 0; i < MAXN; i++) {
		comb[i][i] = comb[i][0] = 1;
		for (int j = 1; j < i; j++) {
			comb[i][j] = comb[i - 1][j];
			add(comb[i][j], comb[i - 1][j - 1]);
		}
	}

	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		rem[x] = 1;
	}

	dp[0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			add(dp[i], 1ll * comb[i - 1][j - 1] * dp[j - 1] % MOD * dp[i - j] % MOD * (i - j + 2) % MOD);
		}
	}
	
	int c0 = 0, c1 = 0;
	pre[n + n + 1][0] = 1;
	for (int k = n + n; k; k--) {
		if (rem[k]) {
			memcpy(pre[k], pre[k + 1], sizeof(pre[k]));
			for (int i = 0; i <= c1 + 1; i++) {
				for (int j = 1; j <= i; j++) {
					add(pre[k][i], 1ll * comb[c1 - j + 1][i - j] * pre[k + 1][j - 1] % MOD * dp[i - j] % MOD * (i - j + 2) % MOD);
				}
			}
			c1++;
		}
		else {
			for (int i = 0; i <= c1; i++) {
				pre[k][i] = 1ll * pre[k + 1][i] * max(0, i - c0) % MOD;
			}
			c0++;
		}
	}
	int ans = 1ll * pre[1][n] * inv(power(2, n)) % MOD;
	cout << ans << '\n';
}

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