oj.uz

Submission #49988

# Submission time Handle Problem Language Result Execution time Memory
49988 2018-06-06T03:24:14 Z shoemakerjo Tents (JOI18_tents) C++14
100 / 100
 276 ms 142040 KB 
#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.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 4 ms 1260 KB Output is correct
3 Correct 4 ms 1260 KB Output is correct
4 Correct 6 ms 2092 KB Output is correct
5 Correct 4 ms 2092 KB Output is correct
6 Correct 5 ms 2784 KB Output is correct
7 Correct 5 ms 2784 KB Output is correct
8 Correct 5 ms 2980 KB Output is correct
9 Correct 5 ms 2980 KB Output is correct
10 Correct 6 ms 3556 KB Output is correct
11 Correct 5 ms 3556 KB Output is correct
12 Correct 7 ms 4524 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 4 ms 1260 KB Output is correct
3 Correct 4 ms 1260 KB Output is correct
4 Correct 6 ms 2092 KB Output is correct
5 Correct 4 ms 2092 KB Output is correct
6 Correct 5 ms 2784 KB Output is correct
7 Correct 5 ms 2784 KB Output is correct
8 Correct 5 ms 2980 KB Output is correct
9 Correct 5 ms 2980 KB Output is correct
10 Correct 6 ms 3556 KB Output is correct
11 Correct 5 ms 3556 KB Output is correct
12 Correct 7 ms 4524 KB Output is correct
13 Correct 8 ms 8192 KB Output is correct
14 Correct 15 ms 19352 KB Output is correct
15 Correct 176 ms 110488 KB Output is correct
16 Correct 16 ms 110488 KB Output is correct
17 Correct 44 ms 110488 KB Output is correct
18 Correct 59 ms 110488 KB Output is correct
19 Correct 209 ms 126148 KB Output is correct
20 Correct 166 ms 126148 KB Output is correct
21 Correct 111 ms 126148 KB Output is correct
22 Correct 112 ms 126148 KB Output is correct
23 Correct 63 ms 126148 KB Output is correct
24 Correct 276 ms 142040 KB Output is correct
25 Correct 212 ms 142040 KB Output is correct
26 Correct 235 ms 142040 KB Output is correct
27 Correct 256 ms 142040 KB Output is correct