제출 #49241

#제출 시각아이디문제언어결과실행 시간메모리
49241spencercomptonTents (JOI18_tents)C++17
100 / 100
718 ms71456 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[3001][3001];
ll mod = 1000000007LL;
ll go(int rows, int cols){
	if(rows==0 || cols==0){
		return 1LL;
	}
	if(dp[rows][cols]!=-1){
		return dp[rows][cols];
	}
	ll ret = go(rows-1,cols);
	if(cols>=2){
		ret += ((ll)cols*(ll)(cols-1))/2LL*go(rows-1,cols-2);
		ret %= mod;
	}
	if(rows>=2){
		ret += (ll)cols*(ll)(rows-1)*go(rows-2,cols-1);
		ret %= mod;
	}
	ret += 4LL*(ll)cols*go(rows-1,cols-1);
	ret %= mod;
	dp[rows][cols] = ret;
	return ret;
}
int main(){
	for(int a = 0; a<=3000; a++){
		for(int b =0; b<=3000; b++){
			dp[a][b] = -1;
		}
	}
	int r, c;
	cin >> r >> c;
	cout << (go(r,c)+mod-1LL)%mod << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...