Submission #1118219

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118219		vjudge1	Kangaroo (CEOI16_kangaroo)	C++17	6 / 100	1 ms	336 KiB

kangaroo

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

int main() {

  constexpr int MOD = 1000000007;

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

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

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

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

    for (int 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: 0 / 30
• Subtask 3: 0 / 15
• Subtask 4: 0 / 49