제출 #98783

#제출 시각아이디문제언어결과실행 시간메모리
98783luciocfTents (JOI18_tents)C++14
100 / 100
125 ms71036 KiB
#include <bits/stdc++.h>

using namespace std;

const int maxn = 3e3+10;
const long long mod = 1e9+7;

typedef long long ll;

ll dp[maxn][maxn];

int main(void)
{
	int n, m;
	cin >> n >> m;

	for (int i = 0; i < maxn; i++)
		dp[i][0] = dp[0][i] = 1LL;

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			dp[i][j] = dp[i-1][j];

			dp[i][j] = (dp[i][j] + (dp[i-1][j-1]*4LL*(ll)j))%mod;

			if (j >= 2) 
				dp[i][j] = (dp[i][j] + (dp[i-1][j-2] * 1LL*(j*(j-1))/2))%mod;

			if (i >= 2) 
				dp[i][j] = (dp[i][j] + (dp[i-2][j-1] * 1LL*(j*(i-1))))%mod;
		}
	}

	cout << dp[n][m]-1LL << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...