Submission #1294101

#TimeUsernameProblemLanguageResultExecution timeMemory
1294101dragonrobotKangaroo (CEOI16_kangaroo)C++17
100 / 100
29 ms31804 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const ll MOD = 1000000007;

ll addmod(ll a, ll b){ 
    a += b; 
    if(a >= MOD) a -= MOD; 
    return a; 
}

ll mulmod(ll a, ll b){ 
    return (a * b) % MOD; 
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, s, t;
    if(!(cin >> n >> s >> t)) return 0;

    vector<vector<ll>> f(n+2, vector<ll>(n+3, 0));
    f[1][1] = 1;

    for(int i = 2; i <= n; ++i){
        if(i != s && i != t){
            for(int j = 1; j <= n; ++j){
                ll avail = j - (i > s) - (i > t); // replaced int with ll
                if(avail > 0){
                    f[i][j] = addmod(f[i][j], mulmod(f[i-1][j-1], avail));
                }
                if(j+1 <= n){
                    f[i][j] = addmod(f[i][j], mulmod(f[i-1][j+1], j));
                }
            }
        } else {
            for(int j = 1; j <= n; ++j){
                f[i][j] = addmod(f[i][j], f[i-1][j-1]);
                f[i][j] = addmod(f[i][j], f[i-1][j]);
            }
        }
    }

    cout << f[n][1] % MOD << '\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...