제출 #1118195

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1118195		vjudge1	캥거루 (CEOI16_kangaroo)	C++17	100 / 100	35 ms	31840 KiB

kangaroo

// author - alimammadzade

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

signed main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    // system("cls"), freopen("in.txt", "r", stdin);
    int n, s, f, fixed = 0, mod = 1e9 + 7;
    cin >> n >> s >> f;
    vector<vector<int>> dp(n + 1, vector<int>(n + 1));
    dp[1][1] = 1;
    for (int i = 1; i <= n; i++) {
        fixed += (i == s or i == f);
        for (int j = 1; j < i; j++)
            if (i == s or i == f) {
                (dp[i][j + 1] += dp[i - 1][j]) %= mod;
                (dp[i][j] += dp[i - 1][j]) %= mod;
            }
            else {
                (dp[i][j + 1] += (j + 1 - fixed) * dp[i - 1][j]) %= mod;
                (dp[i][j - 1] += (j - 1) * dp[i - 1][j]) %= mod;
            }
    }
    cout << dp[n][1];
}

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