Submission #236887

#TimeUsernameProblemLanguageResultExecution timeMemory
236887islingrTents (JOI18_tents)C++14
100 / 100
180 ms72568 KiB
#include <iostream>
using namespace std;

#define rep(i, a, b) for (ll i = (a); i <= (b); ++i)

using ll = long long;

const int N = 3 << 10, M = 1e9 + 7;
ll dp[N][N];

signed main() {
	int h, w; cin >> h >> w;
	rep(i, 0, h) dp[i][0] = 1;
	rep(j, 0, w) dp[0][j] = 1;
	rep(i, 1, h) {
		rep(j, 1, w) {
			auto add = [&](ll x) {
				dp[i][j] += x;
				if (M <= dp[i][j]) dp[i][j] -= M;
			};
			if (i != 1) add(i * (i - 1) / 2 % M * dp[i - 2][j - 1] % M);
			add(4 * i * dp[i - 1][j - 1] % M);
			add(dp[i][j - 1]);
			if (j != 1) add(i * (j - 1) % M * dp[i - 1][j - 2] % M);
		}
	}
	cout << (dp[h][w] + M - 1) % M;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...