Submission #867209

#TimeUsernameProblemLanguageResultExecution timeMemory
867209botmidimidKangaroo (CEOI16_kangaroo)C++17
100 / 100
47 ms32088 KiB
#include<bits/stdc++.h>

#define ll long long
#define MaxN 2005
#define Mod 1000000007

using namespace std;


int n, s, t;
ll f[MaxN][MaxN];


ll multi(ll a, ll b) {
    a %= Mod; b %= Mod;
    return (a*b) % Mod;
}


ll dp(int i, int j) {
    if (j < 0) return 0LL;
    if (i == 1) return (j == 1);
    if (f[i][j] != -1LL) return f[i][j];

    ll res = 0LL;
    if (i == s || i == t) {
        res = (res + multi(dp(i-1, j-1), 1)) % Mod; // =))
        res = (res + dp(i-1, j)) % Mod;
    }
    else {
        if (i < s && i < t) res = (res + multi(dp(i-1, j-1), j)) % Mod;
        else if (i < s || i < t) res = (res + multi(dp(i-1, j-1), j-1)) % Mod;
        else res = (res + multi(dp(i-1, j-1), j-2)) % Mod;
        res = (res + multi(dp(i-1, j+1), j)) % Mod;
    }
    f[i][j] = res;
    return res;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);


    cin >> n >> s >> t;


    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) f[i][j] = -1LL;
    }
    cout << dp(n, 1) << "\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...