Submission #1294248

#TimeUsernameProblemLanguageResultExecution timeMemory
1294248AzeTurk810Kangaroo (CEOI16_kangaroo)C++20
100 / 100
24 ms31736 KiB
/*
Telebe of Adicto && Mamedov yani AzeTurk810
I see humans but no humanity
*/
#include <iostream>
#include <vector>

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

using ll = long long;
using namespace std;

#define ln '\n'
#define INFi 1e9
#define INFll 1e18
#define int ll
constexpr int MOD = 1e9 + 7;

void solve() {
    int n , cs , cf;
    cin >> n >> cs >> cf;
    vector< vector< int > > dp(n + 1 , vector< int > (n + 1,0));
    dp[1][1] = 1;
    int say = 0;
    for(int i = 1;i <= n;i++) {
        if(i == cs || i == cf)
            say++;
        for(int j = 1;j < i;j++) {
            if(i == cs || i == cf) {
                dp[i][j + 1] += dp[i - 1][j];
                dp[i][j] += dp[i - 1][j];
                dp[i][j + 1] %= MOD;
            } else {
                dp[i][j + 1] += (j + 1 - say) * dp[i - 1][j];
                dp[i][j - 1] += dp[i - 1][j] * (j - 1);
                dp[i][j - 1] %= MOD;
                dp[i][j + 1] %= MOD;
            }
            dp[i][j] %= MOD;
        } 
    }
    cout << dp[n][1] << ln;
}

// Attack on titan<3

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    int t = 1;
//      cin >> t;
    for(int cases = 0 ; cases < t;cases ++) {
        solve();
    }
}
// Just Imaginary
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...