Submission #355453

#	Time	Username	Problem	Language	Result	Execution time	Memory
355453		kostia244	Tents (JOI18_tents)	C++17	100 / 100	210 ms	91884 KiB

tents

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,ssse3")
#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
const int maxn = 3030, mod = 1e9 + 7;
int n, m, f[maxn][maxn], g[maxn][maxn], h[maxn][maxn], C[maxn][maxn], fact[maxn];
int nck(int n, int k) {
	if(k > n || k < 0) return 0;
	return C[n][k];
}
int calc(int N, int X, int Y) {//N total, X paired, Y single
	int ans = nck(N, X)*1ll*nck(N-X, Y)%mod;
	ans = ans*1ll*f[X][0]%mod;
	return ans;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	for(int i = 0; i < maxn; i++)
		for(int j = 0; j <= i; j++)
			if(!j) C[i][j] = 1;
			else C[i][j] = (C[i-1][j] + C[i-1][j-1])%mod;
	fact[0] = 1;
	for(int i = 1; i < maxn; i++) fact[i] = fact[i-1]*1ll*i%mod;
	cin >> n >> m;
	f[0][0] = 1;
	for(int i = 0; i < max(m, n); i++) {
		for(int j = 0; j <= i; j++) {
			(f[i+1][j+1] += f[i][j])%=mod;
			if(j) f[i+1][j-1] = (f[i+1][j-1] + f[i][j]*1ll*j)%mod;
		}
	}
	for(int i = 0; i <= max(m, n); i++) {
		for(int j = 0; j <= max(m, n); j++) {
			if(min(i, j) == 0) h[i][j] = 1;
			else {
				h[i][j] = (h[i-1][j] + h[i-1][j-1]*4ll*j)%mod;
			}
		}
	}
	int ans = mod-1;
	for(int a = 0; a <= max(n, m); a++)
		for(int b = 0; b <= max(n, m); b++) if(n-2*a-b >= 0 && m-2*b-a >= 0) {
			int res = calc(n, 2*a, b)*1ll*calc(m, 2*b, a)%mod;
			res = res*1ll*fact[a]%mod;
			res = res*1ll*fact[b]%mod;
			res = res*1ll*h[n-2*a-b][m-2*b-a]%mod;
			ans = (ans + res)%mod;
		}
	cout << ans << '\n';
}

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