Submission #62732

#	Time	Username	Problem	Language	Result	Execution time	Memory
62732		kingpig9	Tents (JOI18_tents)	C++11	48 / 100	2069 ms	49632 KiB

tents

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 3018;
const int MOD = 1e9 + 7;

//#define debug(...) fprintf(stderr, __VA_ARGS__)
#define debug(...)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

void addeq (int &x, int y) {
	x += y;
	if (x >= MOD) {
		x -= MOD;
	}
}

int add (int x, int y) {
	addeq(x, y);
	return x;
}

int mult (int x, int y) {
	return ll(x) * y % MOD;
}

int mult (int x, int y, int z) {
	return mult(mult(x, y), z);
}

int mult (int x, int y, int z, int w) {
	return mult(mult(x, y), mult(z, w));
}

int cho[MAXN][MAXN];
int fact[MAXN];
int nterm[MAXN][MAXN];
int pwr4[MAXN];

void precomp() {
	for (int i = 0; i < MAXN; i++) {
		cho[i][0] = 1;
		for (int j = 1; j <= i; j++) {
			cho[i][j] = add(cho[i - 1][j], cho[i - 1][j - 1]);
		}
	}

	fact[0] = 1;
	for (int i = 1; i < MAXN; i++) {
		fact[i] = mult(fact[i - 1], i);
	}

	for (int i = 0; i < MAXN; i++) {
		nterm[i][0] = 1;	//start at i = 0 for the same reason 0 choose 0 is 1.
		for (int j = 1; ; j++) {
			int ntop = i + 2 - 2 * j;
			if (ntop < 2) {
				break;
			}
			nterm[i][j] = mult(nterm[i][j - 1], cho[ntop][2]);
		}
	}

	pwr4[0] = 1;
	for (int i = 1; i < MAXN; i++) {
		pwr4[i] = mult(pwr4[i - 1], 4);
	}
}

int N, M;

int main() {
	precomp();
	scanf("%d %d", &N, &M);

	int ans = 0;
	for (int h = 0; h <= N; h++) {
		for (int v = 0; v <= M; v++) {
			int tcol = 2 * h + v, trow = 2 * v + h;	//# of cols taken, # of rows taken
			if (tcol > M || trow > N) {
				break;
			}

			debug("h = %d, v = %d\n", h, v);
			int nwayv = mult(cho[M][v], nterm[N][v]);
			debug("nwayv = cho[%d][%d] * nterm[%d][%d] = %d\n", M, v, N, v, nwayv);
			int nwayh = mult(cho[N - 2 * v][h], nterm[M - v][h]);
			debug("nwayh = cho[%d][%d] * nterm[%d][%d] = %d\n", N - 2 * v, h, M - v, h, nwayh);

			//now here comes this one
			int nsing = 0;
			int rrem = N - trow, crem = M - tcol;
			for (int i = 0; i <= rrem && i <= crem; i++) {
				debug("nsing += C(%d, %d) * C(%d, %d) * %d! * 4^%d\n", rrem, i, crem, i, i, i);
				addeq(nsing, mult(cho[rrem][i], cho[crem][i], fact[i], pwr4[i]));
			}
			debug("nsing = %d\n", nsing);

			addeq(ans, mult(nwayv, nwayh, nsing));
		}
	}
	printf("%d\n", add(ans, MOD - 1));
}

Compilation message (stderr)

tents.cpp: In function 'int main()':
tents.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~~

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