Submission #670930

#	Time	Username	Problem	Language	Result	Execution time	Memory
670930		Makarooni	Tents (JOI18_tents)	C++14	100 / 100	184 ms	117488 KiB

tents

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define pb(x) push_back(x)
#define mr(x, y) make_pair(x, y)
#define sz(x) (int)x.size()
#define S second
#define F first

const int N = 3e3 + 10;
const int MOD = 1e9 + 7;

long long dp[N][N], c[N][N], fact[N], pw[N];

int main(){
    int h, w;
    cin >> h >> w;
    pw[0] = 1;
    fact[0] = 1;
    for(int i = 0; i < N; i++)
    	c[i][0] = 1;
    for(int i = 1; i < N; i++){
    	fact[i] = fact[i - 1] * i;
    	fact[i] %= MOD;
    	pw[i] = pw[i - 1] * 4;
    	pw[i] %= MOD;
    	for(int j = 1; j <= i; j++){
    		c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
		}
	}
	for(int i = 0; i < N; i++){
		dp[0][i] = 1;
		dp[i][0] = 1;
	}
    for(int i = 1; i <= h; i++){
    	for(int j = 1; j <= w; j++){
				dp[i][j] += dp[i - 1][j];
					dp[i][j] %= MOD;
					if(j >= 2)
						dp[i][j] += c[j][2] * dp[i - 1][j - 2];
					dp[i][j] %= MOD;
					if(i >= 2)
						dp[i][j] += j * (i - 1) * dp[i - 2][j - 1];
					dp[i][j] %= MOD;
		}
	}
	long long ans = 0;
	for(int k = 1; k <= min(h, w); k++){
		ans += ((((((c[h][k] * c[w][k]) % MOD) * fact[k]) % MOD) * dp[h - k][w - k]) % MOD) * pw[k];
		ans %= MOD;
	}
	ans += dp[h][w];
	ans %= MOD;
	if(ans == 0)
        cout << MOD - 1;
    else
        cout << ans - 1;
}

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