Submission #94079

#	Time	Username	Problem	Language	Result	Execution time	Memory
94079		aminra	Tents (JOI18_tents)	C++14	100 / 100	1320 ms	117396 KiB

tents

//tavakol bar khoda
/*
	1. pish miad
	2. pish miad
	3. pish miad
	4. base dg? :(
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MAXN = (int)3007;
const int infint = (int)1e8 + 3;
const int MOD = (int)1e9 + 7;
const ll inf = (ll)1e18;
ll H, W, dp[MAXN][MAXN], C[MAXN][MAXN], fact[MAXN];
ll pwr(ll a, ll b)
{
	if(b == 0)	
		return 1;
	if(b == 1)
		return a;
	ll c = pwr(a, b / 2);
	c = (c * c) % MOD;
	if(b % 2)
		c = (c * a) % MOD;
	return c;
}
ll inv(ll a)
{
	return pwr(a, MOD - 2);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> H >> W;
	//-----------------------------------
	for (int i = 0; i <= W; i++)
		dp[1][i] = i * 4 % MOD + 1, dp[0][i] = 1;
	dp[1][0] = 1;
	
	for (int i = 2; i <= H; i++)
		for (int j = 0; j <= W; j++)
		{
			dp[i][j] = dp[i - 1][j];
			if(j)
				dp[i][j] = dp[i][j] + j * 4 % MOD * dp[i - 1][j - 1] % MOD, dp[i][j] %= MOD;
		}
	//------------------------------------
	fact[0] = 1;
	for (int i = 1; i < MAXN; i++)
		fact[i] = fact[i - 1] * i % MOD;
	C[0][0] = 1;
	for (int i = 1; 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] + C[i - 1][j - 1]) % MOD;
	//-------------------------------------	
	ll ans = 0;
	for (int i = 0; i <= H; i++)
		for (int j = 0; 2 * i + j <= H && i + 2 * j <= W; j++)
		{
			ll nwH = H - 2 * i - j, nwW = W - i - 2 * j;
			ans += C[W][i] * C[H][2 * i] % MOD * fact[2 * i] % MOD * inv(pwr(2, i)) % MOD * C[H - 2 * i][j] % MOD * C[W - i][2 * j] % MOD * fact[2 * j] % MOD * inv(pwr(2, j)) % MOD * dp[nwH][nwW] % MOD,
			ans %= MOD;
		}
	cout << (ans - 1 + MOD) % MOD;
}

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