Submission #100777

#	Time	Username	Problem	Language	Result	Execution time	Memory
100777		TAISA_	Tents (JOI18_tents)	C++14	100 / 100	175 ms	71416 KiB

tents

#include<bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
using namespace std;
using ll=long long;
const ll MOD=1000000007LL;
template<typename T> void chmax(T &a,T b){a=max(a,b);}
template<typename T> void chmin(T &a,T b){a=min(a,b);} 
vector<ll> f,fi;
ll mpow(ll x,ll n){
	ll res=1;
	while(n>0){
		if(n&1){
			res*=x;
			res%=MOD;
		}
		x*=x;
		x%=MOD;
		n>>=1;
	}
	return res;
}
void comb(ll n){
	f.resize(n+10);
	fi.resize(n+10);
	f[0]=1;
	for(ll i=1;i<=n;i++){
		f[i]=f[i-1]*i%MOD;
	}
	fi[n]=mpow(f[n],MOD-2);
	for(ll i=n-1;i>=0;i--){
		fi[i]=fi[i+1]*(i+1LL)%MOD;
	}
}
ll ncr(ll n,ll r){
	return f[n]*fi[r]%MOD*fi[n-r]%MOD;
}
int main(){
	ll h,w;cin>>h>>w;
	comb(h+w);
	vector<vector<ll>> dp(h+10,vector<ll>(w+10));
	dp[0][w]=1;
	for(ll i=1;i<=h;i++){
		for(ll j=0;j<=w;j++){
			dp[i][j]+=dp[i-1][j];
			if(j<w){
				dp[i][j]+=dp[i-1][j+1]*(j+1LL)%MOD*4LL%MOD;
				if(j<w-1){
					dp[i][j]+=dp[i-1][j+2]*((j+2LL)*(j+1LL)/2LL)%MOD;
				}
			}
			dp[i][j]%=MOD;
		}
	}
	ll ans=0;
	for(ll i=0;i<=h/2;i++){//横かぶりの個数
		ll s=1;
		for(ll j=h;j>h-i*2;j-=2){
			s*=ncr(j,2);
			s%=MOD;
		}
		for(ll j=0;j<=w;j++){//残り列数
			if(i==0&&j==w)continue;
			if(j<i)continue;
			ans+=dp[h-i*2][j]*s%MOD*ncr(j,i)%MOD;
			ans%=MOD;
		}
	}
	cout<<ans<<endl;
}

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