Submission #899420

#	Time	Username	Problem	Language	Result	Execution time	Memory
899420		MongHwa	Tents (JOI18_tents)	C++17	100 / 100	146 ms	71384 KiB

tents

#include <iostream>
#include <cstring>
using namespace std;

#define ll long long
#define MOD 1000000007

ll dp[3005][3005];

ll go(int x, int y)
{
	if(x == 0 || y == 0)
		return 1;
	
	ll& ret = dp[x][y];
	if(ret != -1)
		return ret;

	ret = 0;
	ret += go(x-1, y);
	ret %= MOD;

	if(y > 0)
		ret += 4*y*go(x-1, y-1) % MOD;
	ret %= MOD;

	if(x > 1 && y > 0)
		ret += (x-1)*y*go(x-2, y-1) % MOD;
	ret %= MOD;

	if(y > 1)
		ret += (y*(y-1))/2 % MOD * go(x-1, y-2);
	ret %= MOD;

	return ret;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	memset(dp, -1, sizeof(dp));

	int h, w;
	cin >> h >> w;

	cout << (go(h, w) - 1 + MOD) % MOD << '\n';
}

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