Submission #1223403

#TimeUsernameProblemLanguageResultExecution timeMemory
1223403siewjhTents (JOI18_tents)C++20
100 / 100
161 ms71348 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 3005;
const ll mod = 1e9 + 7;
ll memo[MAXN][MAXN];
ll dp(ll r, ll c){
	if (r <= 0 || c <= 0) return 1;
	if (memo[r][c] != -1) return memo[r][c];
	ll ans = dp(r - 1, c);
	ans = (ans + 4 * c * dp(r - 1, c - 1)) % mod;
	if (r >= 2) ans = (ans + c * (r - 1) * dp(r - 2, c - 1)) % mod;
	if (c >= 2) ans = (ans + c * (c - 1) / 2 * dp(r - 1, c - 2)) % mod;
	return memo[r][c] = ans;
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll h, w; cin >> h >> w;
	memset(memo, -1, sizeof(memo));
	cout << (dp(h, w) + mod - 1) % mod;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...