Submission #1173760

#TimeUsernameProblemLanguageResultExecution timeMemory
1173760nguyenkhangninh99Tents (JOI18_tents)C++17
100 / 100
76 ms82760 KiB
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int maxn = 5e3 + 5, mod = 1e9 + 7;

int dp[maxn][maxn];


signed main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    
   int n, m; cin >> n >> m;

       for(int i = 0; i <= n; i++) for(int j = 0; j <= m; j++) dp[i][j] = 1;

   for(int i = 1; i <= n; i++){
       for(int j = 1; j <= m; j++){
           dp[i][j] = dp[i][j - 1];
            dp[i][j] += 4 * i * dp[i - 1][j - 1];
            if(i >= 2) dp[i][j] += dp[i - 2][j - 1] * (i) * (i - 1) / 2;
            if(j >= 2) dp[i][j] += dp[i - 1][j - 2] * (j - 1) * i;
            dp[i][j] %= mod;
       }
   }

   cout << (dp[n][m] - 1 + mod) % mod;

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