Submission #44366

#TimeUsernameProblemLanguageResultExecution timeMemory
44366BruteforcemanTents (JOI18_tents)C++11
100 / 100
239 ms36224 KiB
#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
int mem[3003][3003];

long long dp(int H, int W) {
	if(H < 0) return 0;
	if(W < 0) return 0;
	if(H == 0 || W == 0) return 1;
	if(mem[H][W] != -1) return mem[H][W];
	long long ans = 0;
	ans += dp(H - 1, W);
	ans += dp(H - 1, W - 2) * ((W * (W - 1)) / 2); 
	ans += 4LL * dp(H - 1, W - 1) * W;
	ans += dp(H - 2, W - 1) * W * (H - 1);
	ans %= mod;
	return mem[H][W] = ans;
}

int main() {
	memset(mem, -1, sizeof mem);
	int H, W;
	cin >> H >> W;
	long long ans = dp(H, W) - 1;
	if(ans < 0) ans += mod;
	cout << ans << endl;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...