Submission #134029

#TimeUsernameProblemLanguageResultExecution timeMemory
134029tutisTents (JOI18_tents)C++17
100 / 100
175 ms31324 KiB
/*input
4 3
*/
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll modulo = 1000000007;
ll M[3030][3030];
ll f(ll w, ll h)
{
	if (w > h)
		swap(w, h);
	if (M[w][h] != 0)
		return M[w][h];
	if (w == 0)
		return 1;
	if (w == 1)
		return h * (h - 1) / 2 + 4 * h + 1;
	ll ret = f(w, h - 1);
	ret += f(w - 2, h - 1) * ((w) * (w - 1) / 2);
	ret %= modulo;
	ret += f(w - 1, h - 1) * w * 4;
	ret %= modulo;
	ret += f(w - 1, h - 2) * w * (h - 1);
	ret %= modulo;
	return M[w][h] = ret;
}
int main()
{
	ios_base::sync_with_stdio(false);
	ll w, h;
	cin >> w >> h;
	cout << (f(w, h) + modulo - 1) % modulo << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...