Submission #527741

#	Time	Username	Problem	Language	Result	Execution time	Memory
527741		iliaM	Ruins 3 (JOI20_ruins3)	C++17	100 / 100	357 ms	35896 KiB

ruins3

#include <bits/stdc++.h>
using namespace std;
#define cerr cerr << "DEBUG "

constexpr int MOD = 1000 * 1000 * 1000 + 7;

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

int mult(int a, int b) {
	return 1ll * a * b % MOD;
}

int inv(int n) {
	int k = MOD - 2;
	int res = 1;
	for (; k; k >>= 1, n = mult(n, n)) {
		if (k & 1) {
			res = mult(res, n);
		}
	}
	return res;
}

constexpr int N = 3e3 + 10;

int n, dp[N], p[N];
int ncr[N][N];
bool used[N];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	ncr[0][0] = 1;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (i + j) {
				ncr[i][j] = (i ? ncr[i - 1][j] : 0);
				add(ncr[i][j], (i && j ? ncr[i - 1][j - 1] : 0));
			}
		}
	}

	p[0] = 1;
	for (int i = 1; i < N; ++i) {
		for (int j = 0; j < i; ++j) {
			add(p[i], mult(ncr[i - 1][j], mult(i - j + 1, mult(p[j], p[i - j - 1]))));
		}
	}
	
	cin >> n;
	for (int i = 0; i < n; ++i) {
		int x;
		cin >> x;
		used[x] = true;
	}

	dp[0] = 1;
	int cnt[2] = {};

	for (int k = n << 1; k > 0; --k) {
		if (used[k]) {
			for (int i = cnt[1] + 1; i >= 0; --i) {
				for (int j = 0; j < i; ++j) {
					add(dp[i], mult(mult(dp[j], mult(i - j + 1, p[i - j - 1])), ncr[cnt[1] - j][i - j - 1]));
				}
			}
		} else {
			for (int i = 0; i <= cnt[1]; ++i) {
				dp[i] = mult(dp[i], max(0, i - cnt[0]));
			}
		}
		cnt[used[k]]++;
		//cerr << used[k] << '\n';
		/*for (int i = 0; i <= cnt[1]; ++i) {
			cerr << "dp[" << i "] = " << dp[i] << '\n';
		}*/
	}
	
	int pw = 1;
	for (int i = 0; i < n; ++i) {
		pw = mult(pw, 2);
	}

	cout << mult(dp[n], inv(pw));
}

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