제출 #962385

#제출 시각아이디문제언어결과실행 시간메모리
962385abczzTents (JOI18_tents)C++14
100 / 100
127 ms70692 KiB
#include <iostream>
#include <vector>
#define ll long long

using namespace std;

const ll M = 1e9 + 7;
ll h, w, f, dp[3001][3001];
int main() {
  cin >> h >> w;
  for (int i=0; i<=h; ++i) dp[i][0] = 1;
  for (ll i=1; i<=h; ++i) {
    for (ll j=1; j<=w; ++j) {
      if (i != 1) dp[i][j] = dp[i-1][j];
      dp[i][j] += dp[i-1][j-1] * (w-j+1) % M * 4 % M;
      dp[i][j] %= M;
      if (j >= 2) dp[i][j] += dp[i-1][j-2] * ((w-j+2) * (w-j+1) / 2 % M) % M;
      dp[i][j] %= M;
      if (i >= 2) dp[i][j] += dp[i-2][j-1] * (i-1) % M * (w-j+1) % M;
      dp[i][j] %= M;
    }
  }
  for (int j=1; j<=w; ++j) {
    f += dp[h][j];
    f %= M;
  }
  cout << f << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...