Submission #1145381

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145381		SmuggingSpun	Tents (JOI18_tents)	C++20	48 / 100	2105 ms	196560 KiB

tents

#include<bits/stdc++.h>
#define taskname "flagger"
using namespace std;
typedef long long ll;
const int lim = 5e3 + 5;
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, ans = mod - 1, pw_4[lim], C[lim][lim], A[lim][lim], inv_2[lim];
namespace sub12{
	void solve(){
		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;
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
		freopen(taskname".out", "w", stdout);
	}
	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;
		}
	}
	cin >> n >> m;
	sub12::solve();
}

Compilation message (stderr)

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

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