Submission #1151941

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151941		pinbu	Tents (JOI18_tents)	C++20	100 / 100	244 ms	36056 KiB

tents

#include <bits/stdc++.h>
using namespace std;

const int N = 3005;
const long long oo = 1e18;
const int MOD = 1e9 + 7;
void add(int &X, int Y) {
	if ((X += Y) >= MOD) X -= MOD;
}

int n, m;
int dp[N][N];
int DP(int h, int w) {
	if (!h || !w) return 1;
	int &T = dp[h][w];
	if (T >= 0) return T;
	
	T = 1LL * DP(h - 1, w - 1) * w * 4 % MOD;
	add(T, DP(h - 1, w));
	if (w > 1) add(T, 1LL * DP(h - 1, w - 2) * (w * (w - 1) / 2) % MOD);
	if (h > 1) add(T, 1LL * DP(h - 2, w - 1) * (h - 1) * w % MOD);
	return T;
}
void solve(void) {
	cin >> n >> m;
	memset(dp, -1, sizeof dp);
	int ans = DP(n, m) - 1;
	if (ans < 0) ans += MOD;
	cout << ans; 
}

signed main(void) {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int TEST = 1; //cin >> TEST; 
    while (TEST--) solve();
    
    return 0;
}

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