Submission #375686

#	Time	Username	Problem	Language	Result	Execution time	Memory
375686		pit4h	Tents (JOI18_tents)	C++14	100 / 100	265 ms	117356 KiB

tents

#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#ifndef LOCAL
#define cerr if(0)cerr
#endif
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using pii = pair<int, int>;
const ll mod = 1e9+7, inv2 = (mod+1)/2;
const int MAXH = 3001;
ll factorial[MAXH], C[MAXH][MAXH];

ll fpow(ll x, ll p) {
	if(p==0LL) return 1LL;
	ll y = fpow(x, p/2);
	if(p%2==0) {
		return y*y % mod;	
	}
	return y*y % mod * x % mod;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int H, W; cin>>H>>W;

	factorial[0] = 1;
	for(int i=1; i<=max(H, W); ++i) {
		factorial[i] = factorial[i-1] * i % mod;
	}
	C[0][0] = 1;	
	for(int i=1; i<=max(H, W); ++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];
		}
	}

	vector<vector<ll>> dp(H+1, vector<ll>(W+1));
	dp[0][0] = 1;

	for(int i=1; i<=H; ++i) {
		dp[i][0] = 1;
		for(int j=1; j<=W; ++j) {
			dp[i][j] = (dp[i-1][j] + dp[i-1][j-1] * (W - (j-1)) % mod * 4 % mod) % mod;

			if(i>=2) { //column
				dp[i][j] = (dp[i][j] + dp[i-2][j-1] * (H-(i-1)) % mod * (W-(j-1)) % mod) % mod;	
			}
			if(j>=2) { //row
				dp[i][j] = (dp[i][j] + dp[i-1][j-2] * ((W-(j-2)) * (W-(j-1)) / 2) % mod) % mod;
			}
		}
	}

	ll ans = 0;
	for(int j=1; j<=W; ++j) {
		ans = (ans + dp[H][j]) % mod;
	}
	cout<<ans<<'\n';
}

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