Submission #1004025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004025		ByeWorld	Tents (JOI18_tents)	C++14	48 / 100	40 ms	600 KiB

tents

#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
#define ll long long
#define int long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii, int> ipii;
const int MAXN = 1e3+10;
const int INF = 1e18+10;
const int LOG = 19;
const int MOD = 1e9+7;
const int SQRT = 450;
const vector<int> NOL = {};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const vector<int> dx = {1, -1, 0, 0};
const vector<int> dy = {0, 0, 1, -1};
int sum(int a, int b){
	return (a+b)%MOD;
}
int mul(int a, int b){
	return (a*b)%MOD;
}
int expo(int a, int b){
	if(b==0) return 1;
	int te = expo(a, b/2); te = mul(te, te);
	return (b%2 ? mul(te, a) : te); 
}
void chsum(int &a, int b){
	a = (a+b)%MOD;
}
void chmul(int &a, int b){
	a = (a*b)%MOD;
}

int h, w, ANS = 0;
int fac[MAXN], inv[MAXN], facc[MAXN];
int C(int x, int y){
	if(x < y) return 0;
	return mul(fac[x], mul(inv[y], inv[x-y]));
}
signed main(){
	// ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	fac[0] = 1; inv[0] = 1; fac[1] = 1; inv[1] = 1;
	facc[0] = 1; facc[1] = 1;
	for(int i=2; i<=1000; i++){
		fac[i] = mul(i, fac[i-1]); facc[i] = mul(i, facc[i-2]);
		inv[i] = expo(fac[i], MOD-2);
	}
	cin >> h >> w;
	for(int i=0; i<=h; i++){ // occupied rows
		for(int j=0; j<=w; j++){ // occupied column
			if(2*i+j>w || i+2*j>h) continue;
			int row = mul(C(h, i), C(w, 2*i));
			if(i != 0) row = mul(row, mul(fac[i], facc[2*i-1]));
			int col = mul(C(w-2*i, j), C(h-i, 2*j));
			if(j != 0) col = mul(col, mul(fac[j], facc[2*j-1]));

			int W = w-2*i-j, H = h-i-2*j;
			int te = 1, nw = 1;
			for(int k=1; k<=min(W, H); k++){
				chmul(nw, mul(W-k+1, H-k+1));
				chsum(te, mul(expo(4, k), mul(nw, inv[k])));
			}

			// cout << i << ' ' << j << ' '<< row << ' '<< col<< ' '<< te << " p\n";
			// cout << C(h-i, 2*j) << " c\n";
			chsum(ANS, mul(row, mul(col, te)));
		}
	}
	cout << (ANS+MOD-1)%MOD << '\n';
}

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