Submission #1297156

#TimeUsernameProblemLanguageResultExecution timeMemory
1297156ayazKangaroo (CEOI16_kangaroo)C++20
100 / 100
20 ms23524 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

#define ll long long
#define int ll
#define ld long double
#define pii pair<int,int>
#define all(x) (x).begin(), (x).end()
#define isz(x) (int)(x.size())
#define vi vector<int>
#define vvi vector<vi>
#define ost tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update>

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());


const int sz = 2200, inf = 1000000000;
const ll mod = 1000000007, INF = 1000000000000000000;

int dp[sz][sz];
void solve(int tc) {
  int n, cs, cf;
  cin >> n >> cs >> cf;
  dp[1][1] = 1;
  int cnt = 0;
  for (int i = 1; i <= n; i++) {
    if (i == cs || i == cf)
      cnt++;
    for (int j = 1; j < i; j++) {
      if (i == cs || i == cf) {
        dp[i][j+1] += dp[i-1][j];
        dp[i][j] += dp[i-1][j];
        dp[i][j+1] %= mod;
        dp[i][j] %= mod;
      } else {
        dp[i][j+1] += (j + 1 - cnt) * dp[i-1][j];
        dp[i][j-1] += (j - 1) * dp[i-1][j];
        dp[i][j+1] %= mod;
        dp[i][j-1] %= mod;
      }
    }
  }
  cout << dp[n][1] << '\n';
}
void precompute() {}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
#ifdef LOCAL
  freopen("err.log", "w", stderr);
  freopen("in.txt", "r", stdin);
#endif
  precompute();

  int t = 1;
  // cin >> t;
  for (int tc = 1; tc <= t; tc++) solve(tc);
  return 0;    
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...