Submission #798196

#	Time	Username	Problem	Language	Result	Execution time	Memory
798196		vjudge1	Tents (JOI18_tents)	C++14	100 / 100	59 ms	70684 KiB

tents

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std ;
const ll N = 3000, mod = 1e9 + 7 ;
ll dp[N + 1][N + 1] ;
signed main()
{
    ios_base::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
    ll n, m ;
    cin >> n >> m ;
    for(ll j = 0 ; j <= N ; j++)
        dp[0][j] = dp[j][0] = 1 ;
    for(ll i = 1 ; i <= n ; i++)
        for(ll j = 1 ; j <= m ; j++)
        {
            dp[i][j] += dp[i - 1][j] ;
            dp[i][j] += dp[i - 1][j - 1] * 4ll * j ;
            if(j >= 2)
                dp[i][j] += dp[i - 1][j - 2] * (j * (j - 1) / 2ll) ;
            if(i >= 2)
                dp[i][j] += dp[i - 2][j - 1] * (j * (i - 1)) ;
            dp[i][j] %= mod ;
        }
    cout << (dp[n][m] - 1 + mod) % mod ;
    return 0 ;
}

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