Submission #529118

#	Time	Username	Problem	Language	Result	Execution time	Memory
529118		8e7	Tents (JOI18_tents)	C++17	100 / 100	138 ms	117280 KiB

tents

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ...b ){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 3005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
void madd(int &x, int v) {
	x += v - mod; x += mod & (x>>31);
}
ll comb[maxn][maxn], fac[maxn], dp[maxn][maxn];
ll c(int n, int m) {
	if (m > n || m < 0) return 0;
	return comb[n][m];
}
int main() {
	io

	fac[0] = 1;
	for (int i = 1;i < maxn;i++) fac[i] = fac[i-1] * i % mod;
	comb[0][0] = 1;
	for (int i = 1;i < maxn;i++) {
		for (int j = 0;j <= i;j++) {
			comb[i][j] = (comb[i-1][j] + (j ? comb[i-1][j-1] : 0)) % mod;
		}
	}
	int n, m;
	cin >> n >> m;
	
	dp[0][0] = 1;
	for (int i = 0;i <= n;i++) {
		for (int j = 0;j <= m;j++) {
			if (i == 0 || j == 0) dp[i][j] = 1;
			else {
				if (i > 1) dp[i][j] += c(i, 2) * dp[i-2][j-1] % mod;
				if (j > 1) dp[i][j] += dp[i-1][j-2] * i % mod * (j - 1) % mod;
				dp[i][j] += 4 * i * dp[i-1][j-1] % mod;
				dp[i][j] += dp[i][j-1];
				dp[i][j] %= mod;
			}
		}
	}
	
	cout << (dp[n][m]+mod-1)%mod << endl;
}

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