제출 #45862

#제출 시각아이디문제언어결과실행 시간메모리
45862khohkoTents (JOI18_tents)C++17
100 / 100
292 ms82812 KiB
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
#define ll long long
#define lol long long
#define pb push_back
//#define mp make_pair
#define fr first
#define sc second
#define MAX ((lol)(1e9+100))
#define MX ((lol)(4e9+100))
#define ARRS ((lol)(5e5+100))
#define MOD ((lol)(1e9+7))
#define EP ((double)(1e-9))
#define EPS ((double)(1e-8))
#define pb push_back
#define PI ((double)3.141592653)
#define LG 21

ll dp[4000][4000];


ll go(ll n,ll m){
    if(n<0||m<0)return 0;
    if(n==0||m==0)return 1;
    if(dp[n][m]>=0)return dp[n][m];
   // cout<<m*(m-1)/2<<endl;
    //        10              1*1
    dp[n][m]=go(n-1,m)+m*(m-1)/2*go(n-1,m-2)+m*(n-1)*go(n-2,m-1)+m*4*go(n-1,m-1);
   // cout<<n<<" "<<m<<" "<<dp[n][m]<<endl;
    dp[n][m]%=MOD;
    return dp[n][m];
}


int main(){
    #ifdef KHOKHO
        freopen("in.in","r",stdin);
        freopen("out.out","w",stdout);
    #endif // KHOKHO
    ios::sync_with_stdio(0);
    ll n,m;
    cin>>n>>m;
    for(int i=0; i<=n; i++){
        for(int j=0; j<=m; j++){
            dp[i][j]=-1;
        }
    }
    cout<<go(n,m)-1;

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...