Submission #1351176

#TimeUsernameProblemLanguageResultExecution timeMemory
1351176guardianecTents (JOI18_tents)C++20
100 / 100
54 ms70884 KiB
#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll dp[3007][3007];
const ll MOD = 1e9+7;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll h,w;
    cin >> h >> w;
    for (int i=0; i<=h; i++) dp[i][0] = 1;
    for (int j=0; j<=w; j++) dp[0][j] = 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]+dp[i-1][j-1]*j*4)%MOD;
            if (j>=2) {
                ll k = (j*(j-1)/2)%MOD;
                dp[i][j] = (dp[i][j]+dp[i-1][j-2]*k)%MOD;
            }
            if (i>=2) {
                ll k = (j*(i-1))%MOD;
                dp[i][j] = (dp[i][j]+dp[i-2][j-1]*k)%MOD;
            }
        }
    }

    cout << (dp[h][w]-1+MOD)%MOD;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...