제출 #536360

#제출 시각아이디문제언어결과실행 시간메모리
536360Old_PawnKangaroo (CEOI16_kangaroo)C++14
0 / 100
13 ms31572 KiB
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
long long memo[2001][2001];

long long dp(int i, int j, const int& n, const int& st, const int& ending) {
    if (i == n) {
        if (j == 1) return 1;
        return 0;
    }
    if (memo[i][j] != -1) {
        return memo[i][j];
    }
    long long res = 0;
    long long r1 = 0;
    long long r2 = 0;
    if (i == st || i == ending) {
        if (j >= 1)
            r1 = dp(i + 1, j, n , st, ending);
        r2 = dp(i + 1, j + 1, n ,st, ending);
    } else {
        if (j >= 2)
            r1 = ((j - 1 + mod) * dp(i + 1, j - 1, n, st, ending))%mod;
        int ed = (i>st) + (i>ending);
        int tot  = (j - ed <= 0)?1: j - ed;
        r2 = (tot * dp(i + 1,j + 1, n, st, ending))%mod;
    }
    res = (r1 + r2)%mod;
    memo[i][j] = res;

    return res;
}

int main() {
    int n, st, ending;
    cin >> n >> st >> ending;
    st--;
    ending--;
    memset(memo, -1, sizeof(memo));
    cout << dp(0 ,0, n, st, ending) << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...