Submission #1173041

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173041		VMaksimoski008	Tents (JOI18_tents)	C++20	100 / 100	202 ms	71328 KiB

tents

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;

int n, m;
ll dp[3005][3005];

ll coef(ll x) {
    x = x * (x - 1) / 2;
    return x % mod;
}

ll f(int r, int c) {
    if(r == n + 1) return 1;
    if(dp[r][c] != -1) return dp[r][c];

    ll ans = f(r+1, c);
    //random nebitno
    if(c >= 1) ans = (ans + f(r+1, c-1) * 4ll * c) % mod;
    //EW
    if(c >= 2) ans = (ans + f(r+1, c-2) * coef(c)) % mod;
    //NS
    if(c >= 1) ans = (ans + f(r+2, c-1) * 1ll * c * (n - r)) % mod;

    return dp[r][c] = ans;
}

signed main() {
    memset(dp, -1, sizeof(dp));
    cin >> n >> m;
    cout << (f(1, m) - 1 + mod) % mod << '\n';
}

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