Submission #1223753

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223753		chaeryeong	Tents (JOI18_tents)	C++20	48 / 100	2100 ms	98368 KiB

tents

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
int add (int a, int b) {
	a += b; if (a >= MOD) a -= MOD;
	return a;
}
int sub (int a, int b) {
	a -= b; if (a < 0) a += MOD;
	return a;
}
int mul (int a, int b) {
	return (a * 1ll * b) % MOD;
}
int power (int a, int b) {
	if (!b) return 1;
	int u = power(a, b >> 1);
	u = mul(u, u);
	if (b & 1) u = mul(u, a);
	return u;
}
const int N = 5000;
int fact[N + 1], inv[N + 1];
int nCr (int a, int b) {
	return mul(fact[a], mul(inv[b], inv[a - b]));
}
int f[N + 1][N + 1], pw4[N + 1];
int ans2 (int a, int b) {
	if (a == 0 || b == 0) {
		return a + b == 0;
	}
	if ((a + b) % 3 != 0) {
		return 0;
	}
	return mul(f[a][b], inv[(a + b) / 3]);
}
int ans (int a, int b) {
	int ret = 0;
	for (int i = 0; i <= min(a, b); i++) {
		ret = add(ret, mul(pw4[i], mul(nCr(a, i), mul(nCr(b, i), mul(fact[i], ans2(a - i, b - i))))));
	}
	return ret;
}
void solve () {
	fact[0] = 1;
	for (int i = 1; i <= N; i++) {
		fact[i] = mul(i, fact[i - 1]);
	}
	inv[N] = power(fact[N], MOD - 2);
	for (int i = N - 1; i >= 0; i--) {
		inv[i] = mul(i + 1, inv[i + 1]);
	}
	pw4[0] = 1;
	for (int i = 1; i <= N; i++) {
		pw4[i] = mul(4, pw4[i - 1]);
	}
	f[0][0] = 1;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (i >= 2) {
				f[i][j] = add(f[i][j], mul(nCr(i, 2), mul(j, f[i - 2][j - 1])));
			}
			if (j >= 2) {
				f[i][j] = add(f[i][j], mul(i, mul(nCr(j, 2), f[i - 1][j - 2])));
			}
		}
	}
	int h, w; cin >> h >> w;
	int sum = 0;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			sum = add(sum, mul(nCr(h, i), mul(nCr(w, j), ans(h - i, w - j))));
		}
	}
	cout << sum << '\n';
}
signed main () {
	ios::sync_with_stdio(0); cin.tie(0);
	int tc = 1; //cin >> tc;
	while (tc--) solve();
}

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