Submission #985547

#	Time	Username	Problem	Language	Result	Execution time	Memory
985547		alextodoran	Tents (JOI18_tents)	C++17	100 / 100	85 ms	35676 KiB

tents

/**
 _  _   __  _ _ _  _  _ _
 |a  ||t  ||o    d | |o  |
| __    _| | _ | __|  _ |
| __ |/_  | __  /__\ / _\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 3000;
const int MOD = (int) 1e9 + 7;

void add (int &x, const int &y) {
    x += y;
    if (x >= MOD) {
        x -= MOD;
    }
}

int N, M;
int dp[N_MAX + 2][N_MAX + 2];

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

    cin >> N >> M;
    for (int n = 0; n <= N; n++) {
        dp[n][0] = 1;
    }
    for (int m = 0; m <= M; m++) {
        dp[0][m] = 1;
    }
    for (int n = 1; n <= N; n++) {
        for (int m = 1; m <= M; m++) {
            dp[n][m] = dp[n - 1][m];
            add(dp[n][m], (ll) dp[n - 1][m - 1] * m * 4 % MOD);
            if (m >= 2) {
                add(dp[n][m], dp[n - 1][m - 2] * ((ll) m * (m - 1) / 2 % MOD) % MOD);
            }
            if (n >= 2) {
                add(dp[n][m], (ll) dp[n - 2][m - 1] * m % MOD * (n - 1) % MOD);
            }
        }
    }
    cout << (dp[N][M] - 1 + MOD) % MOD << "\n";

    return 0;
}

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