Submission #514864

#TimeUsernameProblemLanguageResultExecution timeMemory
514864losmi247Kangaroo (CEOI16_kangaroo)C++14
100 / 100
34 ms22980 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2005;
const int mod = 1000000007;

ll n,s,e;
ll dp[N][N];

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

    /*freopen("kangaroo.in","r",stdin);
    freopen("kangaroo.out","w",stdout);*/

    cin >> n >> s >> e;

    dp[0][0] = 1;
    for(int i = 1; i <= n; i++){
        for(ll j = 1; j <= i; j++){
            if(i == s){
                /// create a new component at the beginning or just put it at the beginning
                dp[i][j] += dp[i-1][j-1]+dp[i-1][j];
                dp[i][j] %= mod;
                continue;
            }
            if(i == e){
                /// create a new component at the end or just put it at the end
                dp[i][j] += dp[i-1][j-1]+dp[i-1][j];
                dp[i][j] %= mod;
                continue;
            }

            /// create a new component
            dp[i][j] += (dp[i-1][j-1]*(j-(i > s)-(i > e)))%mod;
            dp[i][j] %= mod;
            /// we can't put new elements at the ends or the beginnings of existing components
            /// merge two components - always valid
            dp[i][j] += (dp[i-1][j+1]*j)%mod;
            dp[i][j] %= mod;
        }
    }

    cout << dp[n][1] << 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...