Submission #543473

#	Time	Username	Problem	Language	Result	Execution time	Memory
543473		jesus_coconut	Tents (JOI18_tents)	C++17	100 / 100	325 ms	36092 KiB

tents

#include <bits/stdc++.h>
#define F first
#define S second
#define all(a) begin(a), end(a)
#define pb push_back
#define eb emplace_back
using namespace std;

using ll = long long;

int const MOD = 1e9 + 7;
int const N = 3009;
int inv2 = (MOD + 1) / 2;
int add(ll a, ll b) {
    ll ret = (a + b) % MOD;
    if (ret < 0) ret += MOD;
    return ret;
}

int mul(ll a, ll b) {
    ll ret = (a * b) % MOD;
    if (ret < 0) ret += MOD;
    return ret;
}

int memo[N][N];
int f(int n, int m) {
    if (n == 0 || m == 0) return 1;
    /*if (min(n, m) == 1) {
        if (m == 1) swap(n, m);
        int mC2 = mul(mul(m, m - 1), inv2);
        return add(mul(4, m), mC2);
    }*/
    if (memo[n][m] != -1) return memo[n][m];
    int mC2 = mul(mul(m, m - 1), inv2);
    memo[n][m] = 0;
    memo[n][m] = add(memo[n][m], f(n-1, m));
    memo[n][m] = add(memo[n][m], mul(mul(4, m), f(n - 1, m - 1)));
    if (m >= 2) memo[n][m] = add(memo[n][m], mul(mC2, f(n - 1, m - 2)));
    if (n >= 2) memo[n][m] = add(memo[n][m], mul(mul(m, n - 1), f(n - 2, m - 1)));
    return memo[n][m];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    for (auto &arr : memo)
        memset(arr, -1, sizeof arr);
    int H, W;
    cin >> H >> W;
    cout << add(f(H, W), -1) << '\n';


    return 0;
}

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