Submission #716691

#	Time	Username	Problem	Language	Result	Execution time	Memory
716691		Sohsoh84	Tents (JOI18_tents)	C++17	100 / 100	288 ms	71380 KiB

tents

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;

const ll MAXN = 3e3 + 10;
const ll MOD = 1e9 + 7;
const ll INV2 = (MOD + 1) / 2;

inline ll poww(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if (b & 1) ans = ans * a % MOD;
		b >>= 1;
		a = a * a % MOD;
	}

	return ans;
}

ll fact[MAXN], inv[MAXN], n, m, dp[MAXN][MAXN];;

inline ll C(ll k, ll n) {
	if (k < 0 || k > n) return 0;
	return fact[n] * inv[k] % MOD * inv[n - k] % MOD;
}

inline ll calc(ll n, ll m, ll k) {
	return C(k, n) * C(2 * k, m) % MOD * fact[2 * k] % MOD * poww(INV2, k) % MOD;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	ll ans = 0;
	fact[0] = inv[0] = 1;
	for (int i = 1; i < MAXN; i++) {
		fact[i] = fact[i - 1] * i % MOD;
		inv[i] = poww(fact[i], MOD - 2);
	}

	for (int i = 0; i < MAXN; i++) {
		for (int j = 0; j < MAXN; j++) {
			if (i == 0 || j == 0) {
				dp[i][j] = 1;
				continue;
			}

			dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1] * j * 4) % MOD;
		}
	}

	cin >> n >> m;
	for (int i = 0; i <= n; i++) {
		for (int j = 0; 2 * i + j <= m && i + 2 * j <= n; j++) {
			ll tans = calc(n, m, i) * calc(m - 2 * i, n - i, j) % MOD * dp[n - i - 2 * j][m - 2 * i - j] % MOD;
			ans = (ans + tans) % MOD;
		}
	}

	cout << (ans + MOD - 1) % MOD << endl;
	return 0;
}

• Subtask 1: 48 / 48
• Subtask 2: 52 / 52