Submission #134029

#	Time	Username	Problem	Language	Result	Execution time	Memory
134029		tutis	Tents (JOI18_tents)	C++17	100 / 100	175 ms	31324 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;
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";
}

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