Submission #478344

#	Time	Username	Problem	Language	Result	Execution time	Memory
478344		daongocha	Tents (JOI18_tents)	C++14	100 / 100	138 ms	117548 KiB

tents

#include <bits/stdc++.h>

#define int long long

#define fileopen(a, b) freopen(((std::string)a + ".inp").c_str(), "r", stdin); freopen(((std::string)b + ".out").c_str(), "w", stdout);
#define fileopen1(a) freopen(((std::string)a + ".inp").c_str(), "r", stdin); freopen(((std::string)a + ".out").c_str(), "w", stdout);

#ifdef PICHU_LOCAL_DEF
	#include <chrono>
#endif

using namespace std;

const int MAXN = 3005, MOD = 1e9 + 7;
int C[MAXN][MAXN]; 
int dp[MAXN][MAXN];
int fact[MAXN * 5];
int inv[MAXN * 5];

int power(int x, int n) {
	int res = 1;
	while (n) {
		if (n & 1) (res *= x) %= MOD;
		(x *= x) %= MOD;
		n >>= 1;
	}
	return res;
}

void prec() {
	for (int i = 0; i < MAXN; i++)
		for (int j = 0; j <= i; j++) {
			if (j == 0 || j == i) C[i][j] = 1;
			else C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
		}
}

signed main() {
	#ifdef PICHU_LOCAL_DEF
		chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
	#endif

	#ifndef PICHU_LOCAL_DEF
		//fileopen1("LAH");
	#endif

	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	fact[0] = 1;
	inv[0] = 1;
	for (int i = 1; i < 10000; i++) fact[i] = fact[i - 1] * i % MOD, inv[i] = power(power(2, i), MOD - 2);

	for (int r = 0; r < MAXN; r++) {
		for (int c = 0; c < MAXN; c++) {
			if (!r || !c) dp[r][c] = 1;
			else dp[r][c] = (r * 4 * dp[r - 1][c - 1] + dp[r][c - 1]) % MOD;
		}
	}

	prec();

	int n, m;
	cin >> n >> m;

	int ans = 0, cnt = 0;
	for (int rows = 0; rows <= min(m / 2, n); rows++) {
		int max_cols = m - 2 * rows;
		int rem = n - rows; 
		for (int cols = 0; cols <= min(rem / 2, max_cols); cols++) {
			int emp_col = m - 2 * rows - cols;
			int emp_row = n - 2 * cols - rows;
			ans += C[n][rows] * C[m][2 * rows] % MOD * fact[2 * rows] % MOD * inv[rows] % MOD * inv[cols] % MOD * C[max_cols][cols] % MOD * C[rem][2 * cols] % MOD * fact[2 * cols] % MOD * dp[emp_col][emp_row] % MOD;	
			ans %= MOD;
		}
	}

	cout << (ans - 1 + MOD) % MOD << '\n';

	#ifdef PICHU_LOCAL_DEF
		chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
		std::cout << std::endl;
		std::cout << "Time difference = " << chrono::duration_cast<chrono::milliseconds> (end - begin).count() << "[ms]" << std::endl;
	#endif
}

Compilation message (stderr)

tents.cpp: In function 'int main()':
tents.cpp:65:15: warning: unused variable 'cnt' [-Wunused-variable]
   65 |  int ans = 0, cnt = 0;
      |               ^~~

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