제출 #431278

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
431278		keko37	Tents (JOI18_tents)	C++14	100 / 100	205 ms	63340 KiB

tents

#include<bits/stdc++.h>

using namespace std;

const int MOD = 1000000007;

typedef long long llint;

const int MAXN = 3005;

int add (int a, int b) {a += b; if (a >= MOD) return a - MOD; return a;}
int sub (int a, int b) {a -= b; if (a < 0) return a + MOD; return a;}
int mul (int a, int b) {return (llint) a * b % MOD;}

int n, m;
int fact[MAXN], pot[MAXN];
int nck[MAXN][MAXN], dp[MAXN][MAXN];

void precompute () {
	fact[0] = 1;
	pot[0] = 1;
	for (int i = 1; i < MAXN; i++) {
		fact[i] = mul(fact[i - 1], i);
		pot[i] = mul(pot[i - 1], (MOD + 1) / 2);
	}
	for (int i = 0; i < MAXN; i++) {
		nck[i][0] = nck[i][i] = 1;
		for (int j = 1; j < i; j++) {
			nck[i][j] = add(nck[i - 1][j], nck[i - 1][j - 1]);
		}
	}
	for (int i = 0; i < MAXN; i++) {
		dp[i][0] = dp[0][i] = 1;
	}
	for (int i = 1; i < MAXN; i++) {
		for (int j = 1; j < MAXN; j++) {
			dp[i][j] = add(dp[i - 1][j], mul(4 * j, dp[i - 1][j - 1]));
		}
	}
}

int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	precompute();
	cin >> n >> m;
	int sol = 0;
	for (int a = 0; a <= n; a++) {
		for (int b = 0; b <= m; b++) {
			int x = n - a - 2 * b;
			int y = m - b - 2 * a;
			if (x < 0 || y < 0) continue;
			int val = mul(mul(nck[n][a], nck[m][2 * a]), mul(nck[n - a][2 * b], nck[m - 2 * a][b]));
			val = mul(val, mul(mul(fact[2 * a], pot[a]), mul(fact[2 * b], pot[b])));
			val = mul(val, dp[x][y]);
			sol = add(sol, val);
		}
	}
	cout << sub(sol, 1);
	return 0;
}

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