Submission #763932

#	Time	Username	Problem	Language	Result	Execution time	Memory
763932		minhcool	Tents (JOI18_tents)	C++17	100 / 100	623 ms	143084 KiB

tents

#define local
#ifndef local
#include ""
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 3e5 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

mt19937 rng(1);

int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}

#ifdef local

int fac[N], invfac[N];

int binpw(int base, int pw){
	int ans = 1;
	while(pw){
		if(pw & 1) ans = (ans * base) % mod;
		base = (base * base) % mod;
		pw >>= 1;
	}
	return ans;
}

void prep(){
	fac[0] = invfac[0] = 1;
	for(int i = 1; i <= 100000; i++){
		fac[i] = (fac[i - 1] * i) % mod;
		invfac[i] = binpw(fac[i], mod - 2) % mod;
	}
}

int precal[3005][3005];// what to do when we have i free rows and j free columns. actually we just either confirm (+1) or choose and (i - 1, j - 1)
int pref[3005][3005];

void process(){
	int h, w;
	cin >> h >> w;
	//int ans = 0;
	for(int i = 0; i <= h; i++){
		for(int j = 0; j <= w; j++){
			precal[i][j] = 1;
			if(i > 0 && j > 0) precal[i][j] += pref[i - 1][j - 1] * 4 * j;
			precal[i][j] %= mod;
			//if(i > 0 && j > 0) pref[i][j] = (pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + precal[i][j] + 2 * mod) % mod;
			if(i > 0) pref[i][j] = (pref[i - 1][j] + precal[i][j]) % mod;
			else pref[i][j] = precal[i][j];
			//else if(j > 0) pref[i][j] = (pref[i][j - 1] + precal[i][j]) % mod;
		//	cout << i << " " << j << " " << precal[i][j] << " " << pref[i][j] << "\n";
		}
	}
	int ans = 0;
	for(int cr = 0; cr <= h/2; cr++){
		for(int cl = 0; cl <= w/2; cl++){
			if((cr * 2 + cl) > h) continue;
			if((cr + cl * 2) > w) continue; 
			// when we use 2 * cr rows, we also use cr columns that is not in the cl * 2 columns and vice versa
			int tol = 0;
			int temp = binpw(2, cr); temp = binpw(temp, mod - 2);
			temp = (temp * fac[h]) % mod;
			temp = (temp * invfac[h - 2 * cr]) % mod;
			temp = (temp * fac[w]) % mod;
			temp = (temp * invfac[w - cr]) % mod;	
			int temp2 = binpw(2, cl); temp2 = binpw(temp2, mod - 2);
		//	cout << temp2 << "\n";
			temp2 = (temp2 * fac[w - cr]) % mod;
			temp2 = (temp2 * invfac[w - cr - 2 * cl]) % mod;
		//	cout << temp2 << "\n";
			temp2 = (temp2 * fac[h - 2 * cr]) % mod;
			temp2 = (temp2 * invfac[h - 2 * cr - cl]) % mod;
		//	cout << temp << " " << temp2 << "\n";
			tol = (temp * temp2) % mod;
			tol = (tol * invfac[cl]) % mod;
			tol = (tol * invfac[cr]) % mod;
			//cout << tol << "\n";
			//cout << (h - (cr * 2 + cl)) << " " << (w - (cr + cl))
			tol = (tol * precal[h - (cr * 2 + cl)][w - (cr + cl * 2)]) % mod;
			if(!(cl + cr)) tol = (tol + mod - 1) % mod;
			/*
			int temp3 = min(h - (cr * 2 + cl), w - (cr + cl * 2)), sum = 0;
			for(int single = 0; single <= temp3; single++){
				int ini = binpw(4, single);
				ini = (ini * fac[h - (cr * 2 + cl)]) % mod;
				ini = (ini * invfac[h - (cr * 2 + cl) - single]) % mod;
				ini = (ini * fac[w - (cr + cl * 2)]) % mod;
				ini = (ini * invfac[w - (cr + cl * 2) - single]) % mod;
				ini = (ini * invfac[single]) % mod;
				sum = (sum + ini) % mod;
			}*/
			//if(!(cl | cr)) sum = (sum + mod - 1) % mod;  
			//tol = (tol * sum) % mod;
			//tol = (tol * )
		//	cout << cr << " " << cl << " " << tol << "\n";
			ans = (ans + tol) % mod;
		}
	}
	cout << ans << "\n";
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	prep();
	process();
}
#endif

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