Submission #49581

#	Time	Username	Problem	Language	Result	Execution time	Memory
49581		longcqt	Tents (JOI18_tents)	C++11	100 / 100	828 ms	71572 KiB

tents

#include <bits/stdc++.h>

using namespace std;

const int N = 3e3 + 1;

typedef long long ll;

int h, w;
ll d[N][N], f[N][N];
ll base = 1e9 + 7;

ll p(int n, int m)
{
	if (n*m == 0) return 1;
	if (d[n][m] != -1) return d[n][m];
	ll res = 0;
	res = (res + 4*m*p(n - 1, m - 1)) % base;
	res = (res + p(n - 1, m)) % base;
	if (m >= 2) res = (res + m*(m - 1)/2*p(n - 1, m - 2)) % base;
	if (n >= 2) res = (res + (n - 1)*m*p(n - 2, m - 1)) % base;
	d[n][m] = res;
	return res;
}


int main()
{
	cin >> h >> w;
	memset(d, -1, sizeof(d));
	//memset(f, -1, sizeof(f));
	//cout << p(h, w) <<' ' << p1(h, w) << endl;
	cout << p(h, w) - 1;
}

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