Submission #1118220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118220		vjudge1	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	34 ms	31860 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;

int main() {

  constexpr int64_t MOD = 1000000007;

  int64_t n, cs, cf, fixed = 0;
  cin >> n >> cs >> cf;

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

  for (int64_t i = 1; i <= n; i++) {

    if (i == cs or i == cf) {
      fixed++;
    }

    for (int64_t j = 1; j < i; j++) {
      if (i == cs or i == cf) {
        dp[i][j] += dp[i - 1][j];
        dp[i][j + 1] += dp[i - 1][j];
        dp[i][j] %= MOD;
        dp[i][j + 1] %= MOD;
        continue;
      }
      dp[i][j - 1] += dp[i - 1][j] * (j - 1);
      dp[i][j + 1] += dp[i - 1][j] * (j + 1 - fixed);
      dp[i][j - 1] %= MOD;
      dp[i][j + 1] %= MOD;
    }
  }

  cout << dp[n][1] % MOD << '\n';
}

• Subtask 1: 6 / 6
• Subtask 2: 30 / 30
• Subtask 3: 15 / 15
• Subtask 4: 49 / 49