Submission #1327769

#TimeUsernameProblemLanguageResultExecution timeMemory
1327769HaroldVemenoKangaroo (CEOI16_kangaroo)C++20
100 / 100
37 ms31724 KiB
#include <bits/stdc++.h>

#ifdef GUDEB
    #define D(x) cerr << #x << ": " << (x) << '\n';
    #define ifdeb if(true)
#else
    #define D(x) ;
    #define ifdeb if(false)
#endif

#define all(x) begin(x), end(x)

using namespace std;
using ull = unsigned long long;
using ll = long long;
// #define int ll;

constexpr ll mod = 1000000007;

ll dp[2002][2002];

void solve() {
    int n, s, f;
    cin >> n >> s >> f;
    --s; --f;

    dp[0][0] = 1;
    for(int i = 0; i < n; ++i) {
        if(i == s || i == f) {
            // endpoint merge
            for(int j = 1; j <= n; ++j) {
                dp[i+1][j] += dp[i][j];
                dp[i+1][j] %= mod;
            }
            // endpoint add
            for(int j = 0; j < n; ++j) {
                dp[i+1][j+1] += dp[i][j];
                dp[i+1][j+1] %= mod;
            }
        } else {
            // merge comps
            for(int j = 2; j <= n; ++j) {
                dp[i+1][j-1] += 1ll*(j-1)*dp[i][j] % mod;
                dp[i+1][j-1] %= mod;
            }
            //add comp
            for(int j = 0; j < n; ++j) {
                dp[i+1][j+1] += 1ll*(j+1 - (i > s) - (i > f))*dp[i][j] % mod;
                dp[i+1][j+1] %= mod;
            }
        }
    }

    cout << dp[n][1] << '\n';


}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << setprecision(20);

    solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...