Submission #1100068

#TimeUsernameProblemLanguageResultExecution timeMemory
1100068khepri캥거루 (CEOI16_kangaroo)C++17
100 / 100
33 ms32044 KiB
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2005, M = 1e9 + 7;

int add(int a, int b) { return (a + b + 2 * M) % M; }

int mul(int a, int b) { return (a * b) % M; }

int n, s, e, mem[N][N];

int dp(int i, int j) {
    if (i == n) return j == 1;
    auto &ret = mem[i][j];
    if (~ret) return ret;
    if (i == s || i == e) {
        ret = dp(i + 1, j);
        ret = add(ret, dp(i + 1, j + 1));
    } else {
        ret = mul(dp(i + 1, j + 1), j + 1 - (i > s) - (i > e));
        if (j > 1) ret = add(ret, mul(dp(i + 1, j - 1), j - 1)) % M;
    }
    return ret;
}

void solve() {
    memset(mem, -1, sizeof mem);
    cin >> n >> s >> e;
    --s, --e;
    cout << dp(0, 0) << '\n';
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

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