Submission #1250619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250619		g4yuhg	Tents (JOI18_tents)	C++20	100 / 100	303 ms	117244 KiB

tents

//Huyduocdithitp
#include <bits/stdc++.h>
typedef long long ll;
#define pii pair<ll, ll> 
#define fi first
#define se second
#define TASK "mansion"
#define start if(fopen(TASK".in","r")){freopen(TASK".in","r",stdin);freopen(TASK".out","w",stdout);}
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);
#define N 3005
#define endl '\n'
using namespace std;

const ll mod = 1e9 + 7;

ll h, w, dp[N][N];

// y tuong: dp[i][j] la con i hang, j cot, DANG XET HANG I, ta co bao nhieu cach
// luu y la ta xet 1 hang cu the i, chu khong xet toan bo

void add(ll &u, ll v) {
	u += v;
	if (u >= mod) u -= mod;
	if (u < 0) u += mod;
}

const int MAXN = 3005; 
long long C[MAXN + 1][MAXN + 1];

void build_nCr() {
    for (int n = 0; n <= MAXN; n++) {
        C[n][0] = C[n][n] = 1;
        for (int k = 1; k < n; k++) {
            C[n][k] = (C[n - 1][k - 1] + C[n - 1][k]) % mod;
        }
    }
}

signed main() {
	build_nCr();
    faster;
    
    cin >> h >> w;
    
    for (int i = 0; i <= h; i ++) {
    	for (int j = 0; j <= w; j ++) {
    		if (i == 0 || j == 0) {
    			dp[i][j] = 1;
    			continue;	
    		}
	    	// ko lam j ca
	    	add(dp[i][j], dp[i - 1][j]);
	    	// dat hang
	    	if (j >= 2)
	    		add(dp[i][j], dp[i - 1][j - 2] * C[j][2] % mod);
	    	// dat cot
	    	if (i >= 2) {
	    		add(dp[i][j], dp[i - 2][j - 1] * j % mod * (i - 1) % mod);
	    	}	
	    	add(dp[i][j], j * 4 % mod * dp[i - 1][j - 1] % mod);
    	}
    }
    
    add(dp[h][w], -1);
    
    cout << dp[h][w];
    
    
    return 0;
}

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