Submission #529045

#	Time	Username	Problem	Language	Result	Execution time	Memory
529045		8e7	Tents (JOI18_tents)	C++17	48 / 100	2090 ms	93180 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], cat[maxn][maxn], po[maxn];
ll c(int n, int m) {
	if (m > n || m < 0) return 0;
	return comb[n][m];
}
int main() {
	io
	po[0] = 1;
	for (int i = 1;i < maxn;i++) po[i] = po[i-1] * 4 % mod;
	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;
		}
	}
	cat[0][0] = 1;
	for (int i = 1;i < maxn-1;i++) {
		for (int j = 0;j <= i;j++) {
			if (j) cat[i][j] = (cat[i][j] + cat[i-1][j-1])%mod;
			cat[i][j] = (cat[i][j] + cat[i-1][j+1] * (j+1)%mod)%mod;
		}
	}

	int n, m;
	cin >> n >> m;
	ll ans = 0;
	for (int i = 0;i < maxn;i++) {
		for (int j = 0;j < maxn;j++) {
			if (2*i + j > n || i + 2 * j > m) continue;
			ll val = c(n, 2*i + j) * c(m, i + 2*j) % mod * 
					c(2*i + j, j)%mod * c(i + 2*j, i)%mod * 
					cat[2*i][0]%mod * cat[2*j][0]%mod * fac[i]%mod * fac[j]%mod;
			ll s = 0;
			int sx = n - (2*i+j), sy = m - (i+2*j);
			for (int k = 0;k <= min(sx, sy);k++) {
				s = (s + c(sx, k) * c(sy, k)%mod * fac[k]%mod * po[k]%mod)%mod; 	
				//debug(i, j, sx, sy, k, c(sx, k) * c(sy, k)%mod * fac[k]%mod * po[k]%mod);
			}
			//debug(i, j, val, s);
			debug(i, j, val*s);
			ans = (ans + val * s)%mod;
			//debug(ans);
		}
	}
	cout << (ans+mod-1)%mod << endl;
}

Compilation message (stderr)

tents.cpp: In function 'int main()':
tents.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 0
      |                    ^
tents.cpp:66:4: note: in expansion of macro 'debug'
   66 |    debug(i, j, val*s);
      |    ^~~~~

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