제출 #1308694

#제출 시각아이디문제언어결과실행 시간메모리
1308694pinbuTents (JOI18_tents)C++20
100 / 100
208 ms36000 KiB
#include <bits/stdc++.h>
using namespace std;

const int N = 3005, 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;
}

signed main(void) {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    cin >> n >> m;
    memset(dp, -1, sizeof dp);
    int ans = DP(n, m) - 1;
	if (ans < 0) ans += MOD;
	cout << ans; 
    
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...