Submission #529026

#	Time	Username	Problem	Language	Result	Execution time	Memory
529026		fhvirus	Tents (JOI18_tents)	C++17	48 / 100	2088 ms	24052 KiB

tents

#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll; typedef pair<int, int> pii;
#define pb emplace_back
#define AI(x) begin(x),end(x)
#define ff first
#define ss second
#ifdef OWO
#define debug(args...) LKJ("\033[0;32m[ " + string(#args) + " ]\033[0m", args)
template <class I> void LKJ(I&&x) { cerr << x << endl; }
template <class I, class...T> void LKJ(I&&x, T&&...t) { cerr << x << ", "; LKJ(t...); }
template <class I> void OI(I a, I b) { while (a < b) cerr << *a << " \n"[next(a) == b]; }
#else
#define debug(...) 0
#define OI(...) 0
#endif

const int MOD = 1'000'000'007;
int mad(int u, int v) {
	u += v - MOD;
	u += MOD & (u >> 31);
	return u;
}
int mul(int u, int v) {
	return (ll) u * v % MOD;
}
int mow(int x, int e) {
	int r = 1;
	while (e) {
		if (e & 1) r = mul(r, x);
		x = mul(x, x);
		e >>= 1;
	}
	return r;
}

const int kN = 3003;
int fac[kN], caf[kN], inv[kN];
void init(int n) {
	fac[0] = 1;
	for (int i = 1; i <= n; ++i) fac[i] = mul(fac[i - 1], i);
	caf[n] = mow(fac[n], MOD - 2);
	for (int i = n; i >= 1; --i) caf[i - 1] = mul(caf[i], i);
	for (int i = 1; i <= n; ++i) inv[i] = mul(fac[i - 1], caf[i]);
}
int C(int n, int k) {
	if (0 > k or k > n) return 0;
	return mul(fac[n], mul(caf[k], caf[n - k]));
}
int P(int n, int k) {
	if (0 > k or k > n) return 0;
	return mul(fac[n], caf[n - k]);
}

int H, W, ans;
int tmp[kN][kN];

int solve(int n, int m) {
	if (n > m) swap(n, m);
	if (tmp[n][m] != -1) return tmp[n][m];
	tmp[n][m] = 0;
	for (int i = 0; i <= n; ++i)
		tmp[n][m] = mad(tmp[n][m], mul(mul(C(n, i), P(m, i)), mow(4, i)));
	return tmp[n][m];
}

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> H >> W;
	if (H > W) swap(H, W);
	init(max(H, W));

	for (int i = 0; i <= H; ++i)
		for (int j = 0; j <= W; ++j)
			tmp[i][j] = -1;

	for (int r = 0; r <= H and 2 * r <= W; ++r)
		for (int c = 0; r + 2 * c <= H and 2 * r + c <= W; ++c) {
			int v = mul(C(H, r), mul(P(W, 2 * r), mow(inv[2], r)));
			v = mul(v, mul(C(W - 2 * r, c), mul(P(H - r, 2 * c), mow(inv[2], c))));
			v = mul(v, solve(H - (r + 2 * c), W - (2 * r + c)));
			ans = mad(ans, v);
		}

	cout << mad(ans, MOD - 1) << '\n';

	return 0;
}

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