Submission #67080

#	Time	Username	Problem	Language	Result	Execution time	Memory
67080		Diuven	Tents (JOI18_tents)	C++11	100 / 100	312 ms	36628 KiB

tents

#include <iostream>
using namespace std;
typedef long long ll;

const int MX=3010, MOD=1e9+7;

int h, w, D[MX][MX];

int d(int x, int y){
	int &res=D[x][y];
	if(res>=0) return res;
	res=d(x-1,y);
	res=(res+4LL*d(x-1,y-1)*y)%MOD;
	if(y>=2) res=(res+1LL*d(x-1,y-2)*(y*(y-1)/2))%MOD;
	if(x>=2) res=(res+1LL*d(x-2,y-1)*y*(x-1))%MOD;
	return res;
}

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

	for(int i=1; i<=h; i++) for(int j=1; j<=w; j++) D[i][j]=-1;
	for(int i=0; i<=h; i++) D[i][0]=1;
	for(int j=1; j<=w; j++) D[0][j]=1;

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

	return 0;
}

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