Submission #194102

#TimeUsernameProblemLanguageResultExecution timeMemory
194102rama_pangKangaroo (CEOI16_kangaroo)C++14
0 / 100
31 ms31864 KiB
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint MOD = 1000000007;

int N, S, T;
lint memo[2005][2005];

lint dp(int n, int comp) {
    if (comp < 0) { 
        return 0; 
    }
    if (n == N) { 
        return comp == 0;
    }
    if (memo[n][comp] != -1) {
        return memo[n][comp];
    }

    lint &res = memo[n][comp] = 0;

    if (n == S || n == T) {
        res += dp(n + 1, comp); // add S or T as new component
        res += comp * dp(n + 1, comp - 1); // add S or T as beginning / end. After that we cannot modify it anymore, so ignore it (AKA delete it).
    } else {
        res += dp(n + 1, comp + 1); // add new component
        res += comp * (comp - 1) * dp(n + 1, comp - 1); // join two components
        if (n > S) {
            res += comp * dp(n + 1, comp - 1); // append S to a component, and it cannot be modified further
        }
        if (n > T) {
            res += comp * dp(n + 1, comp - 1); // append T to a component, and it cannot be modified further
        }
    }

    res %= MOD;
    return res;
}

int main() {
    memset(memo, -1, sizeof(memo));
    cin >> N >> S >> T;
    S--, T--;
    cout << dp(0, 0) << "\n";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...