제출 #60066

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
60066		XmtosX	Tents (JOI18_tents)	C++17	100 / 100	425 ms	59308 KiB

tents

#include <bits/stdc++.h>
using namespace std;
long long dp1(long long x,long long rem);
const int N=3003,mod=1e9+7;
int n,m;
long long memo[N][N],memo1[N][N];
long long dp (long long x,long long rem)
{
    if (x==m)
    {
        return (rem!=n);
    }
    long long &ret= memo[x][rem];
    if (ret)
        return ret;
    ret= dp(x+1,rem);
    if (rem>=2)
    {
        ret+= dp(x+1,rem-2)*(rem*(rem-1)/2);
        ret%=mod;
    }
    if (rem>=1)
    {
        ret+= dp(x+1,rem-1)*rem*4;
        ret%=mod;
        if (x+2<=m)
        {
            ret+= (dp(x+2,rem-1)*rem*(m-x-1));
            ret%=mod;
        }
    }
    return ret;
}

int main()
{
    cin >>n>>m;
    cout <<dp(0,n);
    return 0;
}

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