Submission #1255177

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255177		shafi_root	Tents (JOI18_tents)	C++20	100 / 100	206 ms	187928 KiB

tents

/* _In The Name Of God_ */

#include <bits/stdc++.h>
using namespace std;

#define maxs(a, b)			a = max(a, b)
#define mins(a, b)			a = min(a, b)
#define pb						push_back
#define F						first
#define S						second
#define lc						id << 1
#define rc						lc|1
#define mid						((l + r)/2)
#define int                     long long

typedef pair<int, int>     	pii;
typedef long long               	ll;

const ll  MOD    = 1e9  + 7; // 998244353;
const ll  INF    = 1e9  + 1;
const int MXN    = 3e3  + 5;
const int LOG    = 23;

ll Pow(ll a, ll b) { return !b ? 1 : (Pow(a*a %MOD, b/2) * (b&1 ? a : 1)) %MOD; }

int dp[2][MXN][MXN], n, m, C[MXN][MXN];

void _solve() {
    cin >> n >> m;
	dp[0][0][0] = dp[1][0][0] = 1;
	C[0][0] = 1;
	for (int i = 1; i <= max(n, m); i++) dp[0][0][i] = dp[0][i][0] = C[i][0] = 1;
	for (int i = 1; i <= max(n, m); i++) {
		for (int j = 1; j <= i; j++) {
			if (i >= j) C[i][j] = (C[i-1][j] + C[i-1][j-1]) % MOD;
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			dp[0][i][j] += dp[0][i-1][j] + 4ll * j * dp[0][i-1][j-1] % MOD;
			dp[0][i][j] %= MOD;
			if (j >= 2)
			(dp[1][i][j] += dp[1][i-1][j-2] * j * (j-1) / 2) %= MOD;
			if (i >= 2)
			(dp[1][i][j] += dp[1][i-2][j-1] * (i-1) * j) %= MOD;
		}
	}
	ll ans = 0;
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			(ans += dp[0][i][j] * dp[1][n-i][m-j] % MOD * C[n][i] % MOD * C[m][j] % MOD) %= MOD;
		}
	}
	cout << (ans-1+MOD)%MOD << '\n';
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    int _ = 1;
    // cin >> _;
    while (_--) _solve();
    return 0.0;
}

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