Submission #1258604

#TimeUsernameProblemLanguageResultExecution timeMemory
1258604biankKangaroo (CEOI16_kangaroo)C++20
100 / 100
30 ms14152 KiB
#include <bits/stdc++.h>

#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)

using namespace std;

using vi = vector<int>;

const int MAX_N = 2005;
const int MOD = 1000000007;

int dp[MAX_N][MAX_N];

void add(int &x, int v) {
    x += v;
    if (x >= MOD) x -= MOD;
}

int mul(int a, int b) {
    return int(1LL * a * b % MOD);
}

int main() {
    
    int n, s, t;
    cin >> n >> s >> t;
    --s, --t;
    if (s > t) swap(s, t);
    dp[0][0] = 1;
    forn(i, n) forn(g, n) if (dp[i][g]) {
        if (i < s) {
            if (g > 0) add(dp[i + 1][g - 1], mul(dp[i][g], mul(g, g - 1)));
        } else if (i == s) {
            add(dp[i + 1][g], mul(dp[i][g], g));
        } else if (i < t) {
            if (g > 0) add(dp[i + 1][g - 1], mul(dp[i][g], mul(g - 1, g - 1)));
        } else if (i == t) {
            add(dp[i + 1][g], mul(dp[i][g], g - (i < n - 1)));
        } else {
            if (g > 1) add(dp[i + 1][g - 1], mul(dp[i][g], mul(g - 2, g - 1) + (i == n - 1 && g == 2)));
        }
        add(dp[i + 1][g + 1], dp[i][g]);
    }
    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...