답안 #49988

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49988	2018-06-06T03:24:14 Z	shoemakerjo	Tents (JOI18_tents)	C++14	100 / 100	276 ms	142040 KB

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.0 / 48.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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