Submission #452110

#	Time	Username	Problem	Language	Result	Execution time	Memory
452110		JovanB	Tents (JOI18_tents)	C++17	100 / 100	416 ms	31988 KiB

tents

#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;
}

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