Submission #1362360

#TimeUsernameProblemLanguageResultExecution timeMemory
1362360NewtonabcTents (JOI18_tents)C++20
100 / 100
105 ms71368 KiB
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll MOD=1e9+7;
const int N=3e3+10;
ll dp[N][N];
ll nc2(ll n){return ((n*(n-1LL))/2LL)%MOD;}
ll f(ll h,ll w){
    //cout<<"call" <<h <<" " <<w <<"\n";
    if(h<0 || w<0) return 0;
    if(h==0 || w==0) return 1;
    if(dp[h][w]!=-1) return dp[h][w];
    ll ret=0;
    ret=(ret+f(h-1,w))%MOD;
    ret=(ret+f(h-1,w-1)*(ll)w*4LL)%MOD;
    ret=(ret+f(h-1,w-2)*nc2(w))%MOD;
    ret=(ret+f(h-2,w-1)*((ll)w*(ll)(h-1))%MOD)%MOD;
    //cout<<h <<" " <<w <<" " <<ret <<"\n";
    return dp[h][w]=ret;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int h,w; cin>>h >>w;
    for(int i=0;i<=h;i++) for(int j=0;j<=w;j++) dp[i][j]=-1;
    ll ans=f(h,w);
    ans=(ans+MOD-1LL)%MOD;
    cout<<ans;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...