Submission #165761

#TimeUsernameProblemLanguageResultExecution timeMemory
165761jovan_bTents (JOI18_tents)C++17
100 / 100
459 ms32140 KiB
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;

typedef long long ll;

int add(int a, int b){
    return (a+b)%MOD;
}

int mul(int a, int b){
    return ((ll)a*b)%MOD;
}

int pw(int a, int b){
    if(b == 0) return 1;
    int res = pw(a, b/2);
    res = mul(res, res);
    if(b%2) res = mul(res, a);
    return res;
}

int inv[3005];
int fact[3005];
int dp[3005][3005];

int bin(int n, int k){
    if(n < 0 || k < 0 || n < k) return 0;
    int res = fact[n];
    res = mul(res, inv[n-k]);
    res = mul(res, inv[k]);
    return res;
}

int solve(int h, int w){
    if(h < 0 || w < 0) return 0;
    if(h == 0 || w == 0) return 1;
    if(dp[h][w]) return dp[h][w];
    /// hor. par
    dp[h][w] = add(dp[h][w], mul(solve(h-1, w-2), w*(w-1)/2));
    /// ver. par
    dp[h][w] = add(dp[h][w], mul(solve(h-2, w-1), mul(w, h-1)));
    /// samo jedan
    dp[h][w] = add(dp[h][w], mul(4, mul(solve(h-1, w-1), w)));
    /// nista
    dp[h][w] = add(dp[h][w], solve(h-1, w));
    return dp[h][w];
}

int main(){
    ios_base::sync_with_stdio(false);

    fact[0] = inv[0] = 1;
    for(int i=1; i<=3000; i++){
        fact[i] = mul(fact[i-1], i);
        inv[i] = pw(fact[i], MOD-2);
    }
    int h, w;
    cin >> h >> w;
    cout << add(solve(h, w), MOD-1);
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...