Submission #790008

#TimeUsernameProblemLanguageResultExecution timeMemory
790008tch1cherinTents (JOI18_tents)C++17
100 / 100
106 ms35520 KiB
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

void add(int& a, int b) {
  a += b, a -= a >= MOD ? MOD : 0;
}

int main() {
  int H, W;
  cin >> H >> W;
  int dp[H + 1][W + 1] = {};
  for (int N = 0; N <= H; N++) {
    for (int M = 0; M <= W; M++) {
      if (N == 0 || M == 0) {
        dp[N][M] = 1;
        continue;
      }
      add(dp[N][M], dp[N - 1][M]);
      if (N > 0 && M > 0) {
        add(dp[N][M], 4ll * dp[N - 1][M - 1] * M % MOD);
        if (N > 1) {
          add(dp[N][M], 1ll * dp[N - 2][M - 1] * (N - 1) % MOD * M % MOD); 
        }
        if (M > 1) {
          add(dp[N][M], 1ll * dp[N - 1][M - 2] * (1ll * M * (M - 1) / 2 % MOD) % MOD);
        }
      }
    }
  }
  add(dp[H][W], MOD - 1);
  cout << dp[H][W] << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...