Submission #49988

#	Time	Username	Problem	Language	Result	Execution time	Memory
49988		shoemakerjo	Tents (JOI18_tents)	C++14	100 / 100	276 ms	142040 KiB

tents

#include <bits/stdc++.h>

using namespace std;
#define maxd 3005
#define ll long long

const int mod = 1000000007;
int H, W;
ll nomore[maxd][maxd]; //using ll just in case
ll rorem[maxd];
ll colrem[maxd][maxd];
ll facts[maxd];
ll invfacts[maxd];

ll modpow(ll base, ll pc) {
	if (pc == 0) return 1LL;
	if (pc & 1) {
		ll tmp = modpow(base, pc-1LL);
		return (tmp * base) % mod;
	}
	ll tmp = modpow(base, pc/2LL);
	return (tmp*tmp)%mod;
}

ll inv(ll cur) {
	return modpow(cur, mod-2);
}

void dofacts() { //calculate factorials and their inverses
	facts[0] = 1LL;
	invfacts[0] = 1LL;
	for (int i = 1; i < maxd; i++) {
		facts[i] = (facts[i-1]*1LL*i)%mod;
		invfacts[i] = inv(facts[i]);
	}
}

ll choose(int a, int b) {
	//return a combination b
	ll ans = facts[a] * (invfacts[a-b] * invfacts[b] % mod) % mod;
	return ans % mod; // just in case
}

void calcnomore() { //do if we do no more pairing up
	//f(x, 0) = f(0, x) = 1
	//f(x, y) = f(x, y-1) + 4*x*f(x-1, y-1)
	for (int i = 0; i <= max(H, W); i++) {
		nomore[0][i] = nomore[i][0] = 1LL;

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

void calcrorem() { //calculate how many ways you can do x row removals
	for (int i = 0; i <= H; i++) {
		rorem[i] = 0LL; //incase we break
	}
	ll runprod = 1LL; //the running product
	rorem[0] = 1LL; //only one way to remove nothing
	for (int i = 1; i <= H; i++) {
		if (2*i > W) break; //cannot take all of this
		runprod = (runprod * choose(W - i*2 + 2, 2))%mod;
		ll cur = (runprod * choose(H, i))%mod;
		rorem[i] = cur;
	}	
}

void calccolrem() { 
	//calc how many ways you can do y column removals,
	//		 given you already did x row removals
	for (int i = 0; i <= H; i++) {
		for (int j = 0; j <= W; j++) {
			colrem[i][j] = 0LL; //same idea, set to zero in case we break
		}
	}
	for (int i = 0; i <= H; i++) {
		if (2*i > W) break;
		int h = H-i;
		int w = W - 2*i; 
		//little h and w represent slightly changed values
		ll runprod = 1LL;
		colrem[i][0] = 1LL; //one way to remove nothing
		for (int j = 1; j <= W; j++) {
			if (2*i + j > W || i + 2*j > H) break; //something is deficient
			runprod = (runprod * choose(h - j*2 + 2, 2))%mod;
			ll cur =(runprod * choose(w, j))%mod;
			colrem[i][j] = cur;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> H >> W;

	dofacts();
	calcnomore();
	calcrorem();
	calccolrem();

	ll ans = 0LL;
	//looking at doing x row rem and y col rem
	for (int i = 0; i <= H; i++) {
		for (int j = 0; j <= W; j++) {
			ll cur = (rorem[i] * colrem[i][j]) % mod;
			if (cur == 0LL) continue; //do not get index out of bounds
			cur = (cur * nomore[H - i - 2*j][W - 2*i - j]) % mod;
			// cout << i << " " << j << ":   " << cur << endl;
			ans = (ans + cur) % mod;

		}
	}
	// cout << "ans: ";
	ans = (ans + mod - 1LL)%mod; //subtract out the nothing placed case
	cout << ans << endl;
	cin >> ans;

}
//probably some dp 

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