Submission #798081

#	Time	Username	Problem	Language	Result	Execution time	Memory
798081		bonk	Tents (JOI18_tents)	C++14	100 / 100	256 ms	71156 KiB

tents

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 3002;
const ll mod = 1e9 + 7;

ll dp[N][N];

ll multi(ll a, ll b){
    return ((a % mod) * (b % mod)) % mod;
}

ll add(ll a, ll b){
    return (a + b) % mod;
}

ll f(ll x, ll y){
    if(x < 0 || y < 0) return 0;
    if(x == 0 || y == 0) return 1;

    auto &cur = dp[x][y];
    if(cur != -1) return cur;

    cur = add(
            add(
                add(
                    f(x - 1, y),
                    multi(4LL*y, f(x - 1, y - 1))
                ), 
                multi((y*(y - 1LL))/2LL, f(x - 1, y - 2))
            ), 
            multi(y*(x - 1LL), f(x - 2, y - 1))
        );

    return cur;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    memset(dp, -1, sizeof(dp));
    int h, w; cin >> h >> w;

    cout << (f(h, w) - 1LL + mod) % mod << '\n';

    return 0;
}

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