제출 #516224

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
516224		angelo_torres	Tents (JOI18_tents)	C++17	100 / 100	216 ms	117568 KiB

tents

#include <bits/stdc++.h>
#define f(i,j,n) for(ll i = j; i < n; ++i)
#define fr(i,j,n) for(ll i = j; i >= n; --i)
#define sz(v) (int) v.size()
#define ff first
#define ss second
#define endl "\n"

using namespace std;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
const int N = 3e3 + 20;
const int M = 35;
const int inf = 2e9;
const ll mod = 1e9 + 7;

ll mul(ll a,ll b){
	return (a*b)%mod;
}

ll sum(ll a,ll b){
	return (a+b)%mod;
}

ll h,w,dp[N][N],comb[N][N];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> h >> w;
	comb[0][0] = 1;
	f(i,1,max(h,w)+1){
		f(j,0,i+1){
			comb[i][j] = 1;
			if(j == 0) continue;
			comb[i][j] = sum(comb[i-1][j],comb[i-1][j-1]);
		}
	}
	dp[0][0] = 1;
	f(i,1,h+1){
		f(j,1,w+1){
			ll nj = (j*(j-1))>>1;
			nj %= mod;
			dp[i][j] = sum(dp[i][j],mul(4,mul(j,dp[i-1][j-1])));
			if(j > 1) dp[i][j] = sum(dp[i][j],mul(nj,dp[i-1][j-2]));
			if(i > 1) dp[i][j] = sum(dp[i][j],mul(mul(j,i-1),dp[i-2][j-1]));
			// cout << dp[i][j] << " ";
		}
		// cout << endl;
	}
	ll ans = 0;
	f(i,1,h+1){
		f(j,1,w+1) ans = sum(ans,mul(mul(comb[h][i],comb[w][j]),dp[i][j]));
	}
	cout << ans << endl;
	return 0;
}

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