제출 #1360844

#제출 시각아이디문제언어결과실행 시간메모리
1360844vjudge1Tents (JOI18_tents)C++17
100 / 100
54 ms70776 KiB
#include<bits/stdc++.h>
using namespace std;
long long dp[3001][3001];
const int MOD = 1000000007;
int main() {
    int H, W;
    if (!(cin >> H >> W)) return 0;
    for (int j = 0; j <= W; ++j) dp[0][j] = 1;
    for (int i = 0; i <= H; ++i) 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] = (dp[i][j] + 4LL * j % MOD * dp[i-1][j-1]) % MOD;
            if (j >= 2) {
                long long ways = 1LL * j * (j - 1) / 2 % MOD;
                dp[i][j] = (dp[i][j] + ways * dp[i-1][j-2]) % MOD;
            }
            if (i >= 2) {
                long long ways = 1LL * j * (i - 1) % MOD;
                dp[i][j] = (dp[i][j] + ways * dp[i-2][j-1]) % MOD;
            }
        }
    }
    long long result = (dp[H][W] - 1 + MOD) % MOD;
    cout << result << endl;
    return 0;
}
// hello rahidil
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…