Submission #66988

#	Time	Username	Problem	Language	Result	Execution time	Memory
66988		Diuven	Tents (JOI18_tents)	C++11	48 / 100	2076 ms	28556 KiB

tents

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

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

int h, w, C[MX][MX], F[2*MX], T[MX], U[2*MX];

int c(int n, int r){
	if(n<0 || r<0 || n<r) return 0;
	return C[n][r];
}

int f(int h, int w, int a){
	ll res=1;
	res=res*c(h,a)%MOD;
	res=res*c(w,2*a)%MOD;
	res=res*F[2*a]%MOD;
	res=res*T[a]%MOD;
	return res;
}
int g(int h, int w, int a){
	ll res=1;
	res=res*c(h,a)%MOD;
	res=res*c(w,a)%MOD;
	res=res*F[a]%MOD;
	res=res*U[2*a]%MOD;
	return res;
}

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

	for(int i=0; i<MX; i++){
		C[i][0]=C[i][i]=1;
		for(int j=1; j<i; j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;
	}
	F[0]=1;
	for(int i=1; i<2*MX; i++) F[i]=(1LL*F[i-1]*i)%MOD;
	T[0]=1, T[1]=5e8+4;
	for(int i=2; i<MX; i++) T[i]=(1LL*T[i-1]*T[1])%MOD;
	U[0]=1;
	for(int i=1; i<2*MX; i++) U[i]=U[i-1]*2%MOD;


	int ans=0;
	for(int a=0; a<=h; a++){
		for(int b=0; b<=w; b++){
			for(int c=0; c<=h; c++){
				if(a+b+c==0) continue;
				ll now=f(h, w, a);
				now=now*f(w-2*a, h-a, b)%MOD;
				now=now*g(h-a-2*b, w-2*a-b, c)%MOD;
				ans=(ans+now)%MOD;
			}
		}
	}
	cout<<ans<<'\n';
	return 0;
}

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