Submission #1100068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100068		khepri	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	33 ms	32044 KiB

kangaroo

#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();
    }
}

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