제출 #60089

#제출 시각아이디문제언어결과실행 시간메모리
60089HassoonyTents (JOI18_tents)C++17
100 / 100
559 ms71804 KiB
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MX=3009;
const ll mod=1e9+7;
ll n,m,dp[MX][MX];
ll DP(ll x,ll rem){
    if(x>n)return 0;
    if(rem==0)return 1ll;
    if(rem<0)return 0;
    if(x==n)return (rem!=m)*1ll;
    ll &ret=dp[x][rem];if(ret!=-1)return ret;
    ret=DP(x+1,rem)%mod;
    ret=(ret+(DP(x+1,rem-1)*4*rem)%mod)%mod;
    ret=(ret+(DP(x+1,rem-2)*(rem*(rem-1)/2))%mod)%mod;
    ret=(ret+(DP(x+2,rem-1)*rem*(n-x-1))%mod)%mod;
    return ret;
}
int main(){
    cin>>n>>m;
    memset(dp,-1,sizeof(dp));
    cout<<DP(0,m)<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...