Submission #766295

#	Time	Username	Problem	Language	Result	Execution time	Memory
766295		1075508020060209tc	Tents (JOI18_tents)	C++14	48 / 100	139 ms	165708 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[310][310][310];
int cn2(int x){
return ((x*(x-1))/2)%mod;
}

signed main(){
cin>>n>>m;
dp[0][m][0]=1;

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

}

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