Submission #1113164

#TimeUsernameProblemLanguageResultExecution timeMemory
1113164onlk97Tents (JOI18_tents)C++14
100 / 100
131 ms70888 KiB
#include <bits/stdc++.h> #define int long long #define x first #define y second #define pb push_back using namespace std; using pii=pair <int,int>; using tii=pair <pii,int>; const int mod=1e9+7LL; int dp[3010][3010]; void solve(){ int n,m; cin>>n>>m; dp[0][0]=1; for (int i=0; i<n; i++){ for (int j=0; j<=m; j++){ dp[i+1][j]+=dp[i][j]; dp[i+1][j]%=mod; if (j<m){ dp[i+1][j+1]+=4*dp[i][j]*(m-j); dp[i+1][j+1]%=mod; } if (j<m-1){ dp[i+1][j+2]+=dp[i][j]*((m-j)*(m-j-1)/2%mod); dp[i+1][j+2]%=mod; } if (i<n-1&&j<m){ dp[i+2][j+1]+=dp[i][j]*((m-j)*(n-i-1)%mod); dp[i+2][j+1]%=mod; } } } int ans=0; for (int i=0; i<=m; i++) ans=(ans+dp[n][i])%mod; cout<<(ans+mod-1)%mod<<'\n'; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); int t=1; //cin>>t; while (t--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...