Submission #767298

#	Time	Username	Problem	Language	Result	Execution time	Memory
767298		1075508020060209tc	Tents (JOI18_tents)	C++14	100 / 100	83 ms	82768 KiB

tents

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
const int mod=1e9+7;
int n;int m;
int dp[5010][5010];
int cn2(int x){
return ((x*(x-1))/2)%mod;
}


signed main(){
cin>>n>>m;
dp[0][m]=1;
for(int H=1;H<=n;H++){
    for(int W=0;W<=m;W++){

        dp[H][W]=dp[H-1][W];

        dp[H][W]=(dp[H][W]+dp[H-1][W+1]*4*(W+1) )%mod;

        dp[H][W]=(dp[H][W]+dp[H-1][W+2]*cn2(W+2))%mod;

        if(H>=2){
            dp[H][W]=(dp[H][W]+dp[H-2][W+1]*(W+1)%mod*(H-1))%mod;
        }
    }
}
int ans=0;
for(int i=0;i<=m-1;i++){
    ans=(ans+dp[n][i])%mod;
}
cout<<ans<<endl;



}

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