제출 #899420

#제출 시각아이디문제언어결과실행 시간메모리
899420MongHwaTents (JOI18_tents)C++17
100 / 100
146 ms71384 KiB
#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';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...