Submission #194104

#TimeUsernameProblemLanguageResultExecution timeMemory
194104rama_pangKangaroo (CEOI16_kangaroo)C++14
100 / 100
109 ms31992 KiB
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint MOD = 1e9 + 7;

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

lint dp(int n, int comp) {
    if (comp < 0) { 
        return 0; 
    }
    if (n == N - 1) { 
        return comp == 0; // use last piece to merge S and T component
    }
    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); // mege with free component
    } else {
        res += dp(n + 1, comp + 1); // add new component
        res += comp * (comp - 1) * dp(n + 1, comp - 1); // merge two free components
        if (n > S) { // merge start with free
            res += comp * dp(n + 1, comp - 1); // append S to a component, and it cannot be modified further
        }
        if (n > T) { // merge end with free
            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...