제출 #43978

#제출 시각아이디문제언어결과실행 시간메모리
43978MatheusLealVTents (JOI18_tents)C++17
100 / 100
314 ms72800 KiB
#include <bits/stdc++.h>
#define N 3030
#define mod (1000000007)
using namespace std;
typedef long long ll;

ll H, W, dp[N][N];

ll solve(int lf, int cf)
{
	if(lf < 0 || cf < 0) return 0;

	if(!lf || !cf) return 1;

	if(dp[lf][cf] != -1) return dp[lf][cf];

	ll nao_coloca = solve(lf - 1, cf), coloca1 = solve(lf - 1, cf - 1)*4*cf;

	ll coloca2 = solve(lf - 1, cf - 2)*cf*(cf - 1)/2, coloca2row = solve(lf - 2, cf - 1)*cf*(lf - 1);

	return dp[lf][cf] = (nao_coloca + coloca1 + coloca2 + coloca2row)%mod;
}

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

	cin>>H>>W;

	memset(dp, -1, sizeof dp);

	cout<<(solve(H, W) + mod - 1)%mod<<"\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...