Submission #898472

#	Time	Username	Problem	Language	Result	Execution time	Memory
898472		maxFedorchuk	Tents (JOI18_tents)	C++17	100 / 100	174 ms	62924 KiB

tents

#include <bits/stdc++.h>
using namespace std;

const long long MOD=1e9+7;

const long long MX=3300;

long long dp[MX][MX];

long long cntdp(long long n,long long m)
{
    if(n<=0 || m<=0)
    {
        return 1;
    }

    if(dp[n][m])
    {
        return dp[n][m];
    }

    dp[n][m]=cntdp(n-1,m);

    dp[n][m]=(cntdp(n-1,m-1)*4*m+dp[n][m])%MOD;

    dp[n][m]=((cntdp(n-1,m-2)*(m*(m-1)/2))%MOD+dp[n][m])%MOD;

    dp[n][m]=((cntdp(n-2,m-1)*m*(n-1))%MOD+dp[n][m])%MOD;

    return dp[n][m];
}
int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    long long n,m;
    cin>>n>>m;

    cout<<(cntdp(n,m)-1+MOD)%MOD<<"\n";
    return 0;
}

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