Submission #134028

#TimeUsernameProblemLanguageResultExecution timeMemory
134028tutisTents (JOI18_tents)C++17
48 / 100
2025 ms57812 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;
map<pair<ll, ll>, ll>M;
ll f(ll w, ll h)
{
	if (w > h)
		swap(w, h);
	if (M.count({w, h}))
		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...