Submission #1086914

#TimeUsernameProblemLanguageResultExecution timeMemory
1086914GabitussKangaroo (CEOI16_kangaroo)C++17
100 / 100
36 ms31836 KiB
#include <bits/stdc++.h>

using namespace std;

//@formatter:off
using ll = long long;
template<typename T> istream &operator>>(istream &is, vector<T> &a);
template<typename T> ostream &operator<<(ostream &os, vector<T> &a);
//@formatter:on
#define int long long
const int mod = 1e9 + 7;

signed main() {
#ifdef LOCAL
      freopen("input.txt", "r", stdin);
      freopen("output.txt", "w", stdout);
#else
      ios_base::sync_with_stdio(false);
      cin.tie(0);
#endif

      int n, a, b;
      cin >> n >> a >> b;

      a--, b--;

      vector<vector<int>> dp(n + 1, vector<int>(n + 1));
      dp[0][0] = 1;

      for (int i = 0; i < n; ++i) {
            for (int comp = 0; comp < n; ++comp) {
                  if (i == a || i == b) {
                        dp[i + 1][comp + 1] += dp[i][comp];
                        dp[i + 1][comp] += dp[i][comp];
                        dp[i + 1][comp + 1] %= mod;
                        dp[i + 1][comp] %= mod;
                  } else {
                        dp[i + 1][comp + 1] += dp[i][comp] * (comp + 1 - (a <= i) - (b <= i));
                        if (comp > 0)dp[i + 1][comp - 1] += dp[i][comp] * (comp - 1);
                        dp[i + 1][comp + 1] %= mod;
                        dp[i + 1][comp - 1] %= mod;
                  }
            }
      }

      cout << dp[n][1] << "\n";
}

// region POZOR
template<typename T>
ostream &operator<<(ostream &os, vector<T> &a) {
      for (int i = 0; i < a.size(); i++)
            os << a[i] << " \n"[i == a.size() - 1];
      return os;
}

template<typename T>
istream &operator>>(istream &is, vector<T> &a) {
      for (auto &i: a)
            is >> i;
      return is;
}
// endregion
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...