Submission #134028

#	Time	Username	Problem	Language	Result	Execution time	Memory
134028		tutis	Tents (JOI18_tents)	C++17	48 / 100	2025 ms	57812 KiB

tents

/*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";
}

• Subtask 1: 48 / 48
• Subtask 2: 0 / 52