제출 #832466

#제출 시각아이디문제언어결과실행 시간메모리
832466Ahmed_Salah7캥거루 (CEOI16_kangaroo)C++17
100 / 100
44 ms16332 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;
    ret = 0;
    if (i + 1 == s) {
        if (j)
            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) {
        if (j)
            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 > 1)
        ret = add(ret, mul(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...