Submission #1145529

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145529		SmuggingSpun	Tents (JOI18_tents)	C++20	100 / 100	63 ms	35656 KiB

tents

#include<bits/stdc++.h>
#define taskname "C"
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
int power(int a, int b){
	int ans = 1;
	for(; b > 0; b >>= 1, a = 1LL * a * a % mod){
		if(b & 1){
			ans = 1LL * ans * a % mod;
		}
	}
	return ans;
}
void add(int& a, int b){
	if((a += b) >= mod){
		a -= mod;
	}
}
int n, m;
namespace sub1{
	const int lim = 305;
	int ans = mod - 1, pw_4[lim], C[lim][lim], A[lim][lim], inv_2[lim];
	void solve(){
		for(int i = pw_4[0] = 1; i < lim; i++){
			pw_4[i] = (ll(pw_4[i - 1]) << 2LL) % mod;
		}
		inv_2[inv_2[0] = 1] = power(2, mod - 2);
		for(int i = 2; i < lim; i++){
			inv_2[i] = 1LL * inv_2[i - 1] * inv_2[1] % mod;
		}
		for(int i = 0; i < lim; i++){
			C[0][i] = A[0][i] = 1;
		}
		for(int i = 1; i < lim; i++){
			for(int j = 0; j < i; j++){
				C[i][j] = A[i][j] = 0;
			}
			for(int j = i; j < lim; j++){
				C[i][j] = (C[i][j - 1] + C[i - 1][j - 1]) % mod;
				A[i][j] = (ll(A[i][j - 1]) + 1LL * A[i - 1][j - 1] * i) % mod;
			}
		}
		for(int a = m >> 1; a > -1; a--){
			for(int b = n >> 1; b > -1; b--){
				int base = 1LL * C[a][n] * A[a << 1][m - b] % mod * C[b][m] % mod * A[b << 1][n - a] % mod * inv_2[a + b] % mod, coef = 0;
				for(int c = min(n - a - (b << 1), m - b - (a << 1)); c > -1; c--){
					add(coef, 1LL * C[c][m - b - (a << 1)] * A[c][n - a - (b << 1)] % mod * pw_4[c] % mod);
				}
				add(ans, 1LL * base * coef % mod);
			}
		}
		cout << ans;
	}
}
namespace sub2{
	const int lim = 3e3 + 5;
	int dp[lim][lim];
	void solve(){
		for(int i = 0; i < lim; i++){
			dp[0][i] = dp[i][0] = 1;
		}
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= m; j++){
				dp[i][j] = (4LL * j * dp[i - 1][j - 1] + dp[i - 1][j]) % mod;
				if(i > 1){
					add(dp[i][j], 1LL * j * (i - 1) * dp[i - 2][j - 1] % mod);
				}
				if(j > 1){
					add(dp[i][j], ((1LL * j * (j - 1)) >> 1LL) * dp[i - 1][j - 2] % mod);
				}
			}
		}
		cout << (dp[n][m] + mod - 1) % mod;
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n >> m;
	if(n <= 300 && m <= 300){
		sub1::solve();
	}
	else{
		sub2::solve();
	}
}

Compilation message (stderr)

tents.cpp: In function 'int main()':
tents.cpp:80:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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