Submission #194263

#TimeUsernameProblemLanguageResultExecution timeMemory
194263rama_pang캥거루 (CEOI16_kangaroo)C++14
100 / 100
232 ms126428 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][2][2];

lint dp(int n, int comp, int lend, int rend) {
    if (comp < 0) { 
        return 0; 
    }
    if (n == N - 1) { 
        return comp == 0 ? 1 : 0; // use last piece to merge S and T component
    }

    lint &res = memo[n][comp][lend][rend];
    if (res != -1) {
        return res;
    }
    
    res = 0;

    if (n == S) {
        res += dp(n + 1, comp, 1, rend); // make new component
        res += dp(n + 1, comp - 1, 1, rend) * comp; // connect a component to left end
    } else if (n == T) {
        res += dp(n + 1, comp, lend, 1); // make new component
        res += dp(n + 1, comp - 1, lend, 1) * comp; // connect a component to right end
    } else {
        res += dp(n + 1, comp + 1, lend, rend); // add a new component
        res += dp(n + 1, comp - 1, lend, rend) * comp * (comp - 1); // merge two components
        res += dp(n + 1, comp - 1, lend, rend) * comp * lend; // connect component to left end
        res += dp(n + 1, comp - 1, lend, rend) * comp * rend; // connect component to right end
    }

    res %= MOD;
    return res;
}

int main() {
    memset(memo, -1, sizeof(memo));
    cin >> N >> S >> T;
    S--, T--;
    cout << dp(0, 0, 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...