Submission #667181

#	Time	Username	Problem	Language	Result	Execution time	Memory
667181		Kahou	Tents (JOI18_tents)	C++14	100 / 100	225 ms	71204 KiB

tents

#include<bits/stdc++.h>
using namespace std;
#define F first
#define s second
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;

const int mod = 1e9 + 7;
int add(int a, int b) {
	a += b;
	if (a >= mod) a -= mod;
	if (a < 0) a += mod;
	return a;
}
int mul(int a, int b) {
	return 1ll*a*b%mod;
}

const int N = 3005;
int H, W, dp[N][N], dp2[N], C[N][N];

void solve() {
	cin >> H >> W;
	C[0][0] = 1;
	for (int x = 1; x < N; x++) {
		C[x][0] = 1;
		for (int y = 1; y < N; y++) {
			C[x][y] = add(C[x-1][y-1], C[x-1][y]);
		}
	}
	for (int y = 0; y < N; y++) {
		dp[0][y] = 1;
	}
	for (int x = 1; x < N; x++) {
		dp[x][0] = 1;
		for (int y = 1; y < N; y++) {
			dp[x][y] = add(mul(4, mul(dp[x-1][y-1], y)), dp[x-1][y]);
		}
	}
	dp2[0] = 1;
	for (int x = 1; x < N/2; x++) {
		dp2[x] = mul(dp2[x-1], C[2*x][2]);
	}
	int ans = 0;
	for (int x = 0; x <= H; x++) {
		for (int y = 0; y <= W; y++) {
			if (x+2*y > H || 2*x+y > W) continue;

			int tmp = 1;
			tmp = mul(tmp, C[H][x]);
			tmp = mul(tmp, C[W][2*x]);
			tmp = mul(tmp, C[H-x][2*y]);
			tmp = mul(tmp, C[W-2*x][y]);
			tmp = mul(tmp, dp[H-x-2*y][W-2*x-y]);
			tmp = mul(tmp, dp2[x]);
			tmp = mul(tmp, dp2[y]);
			ans = add(ans, tmp);
		}
	}
	cout << ans-1 << endl;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	solve();
	return 0;
}

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