Submission #789266

#TimeUsernameProblemLanguageResultExecution timeMemory
789266cig32캥거루 (CEOI16_kangaroo)C++17
100 / 100
21 ms31948 KiB
#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAXN = 2023;
const int MOD = 1e9 + 7;
int dp[MAXN][MAXN], n, a, b;
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> a >> b;
  if(a > b) swap(a, b);
  dp[1][1] = 1;
  for(int i=2; i<=n; i++) {
    for(int j=1; j<=n; j++) {
      if(i == a || i == b) {
        dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % MOD;
      }
      else if(i < a) {
        dp[i][j] = (j * dp[i-1][j-1] + j * dp[i-1][j+1]) % MOD;
      }
      else if(a < i && i < b) {
        dp[i][j] = ((j-1) * dp[i-1][j-1] + j * dp[i-1][j+1]) % MOD;
      }
      else {
        dp[i][j] = (max(0ll, j-2) * dp[i-1][j-1] + j * dp[i-1][j+1]) % MOD;
      }
    }
  }
  cout << dp[n][1] << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...