Submission #832451

#TimeUsernameProblemLanguageResultExecution timeMemory
832451Ahmed_Salah7캥거루 (CEOI16_kangaroo)C++17
0 / 100
8 ms16084 KiB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2000 + 10, M = 1e6 + 6, mod = 1e9 + 7;

int n;
int dp[N][N];

int add(int a, int b) {
    return (a + b) % mod;
}

int mul(int a, int b) {
    return (1LL * a * b) % mod;
}

int s, e;

int sol(int i, int j) {
    if (i == n)
        return (j == 1);
    int &ret = dp[i][j];
    if (~ret)
        return ret;
    if (i + 1 == s) {
        ret = sol(i + 1, j); // add to the first comp
        ret = add(ret, sol(i + 1, j + 1)); // create new comp
        return ret;
    }
    if (i + 1 == e) {
        ret = sol(i + 1, j); // add to the last comp
        ret = add(ret, sol(i + 1, j + 1)); // create new comp
        return ret;
    }
    // add newComp
    ret = mul(sol(i + 1, j + 1), (j + 1 - (i + 1 < s) + (i + 1 < e)));
    // merge twoComps
    if (j)
        ret = add(ret, sol(i + 1, j - 1) * (j - 1));
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    memset(dp, -1, sizeof dp);
    cin >> n >> s >> e;
    cout << sol(0, 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...